14
$\begingroup$

There is a series of 100 lockers in a school. All of them start closed.

Students number 1 to 100 flip an even, two sided coin.

If the coin lands on heads, they go through each locker corresponding to their number's multiple and opens it. If it is already open, the student closes the locker.

If the coin lands on tails, they go through each locker corresponding to their number's factors and opens it. If it is already open, the student closes the locker.

Every single student, one at a time, goes through this procedure.

What is the likelihood that all lockers that are multiples of 6 are open at the end of the procedure?

*Assume the students do not use the lockers at all except for this loop.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Is there a 'clean' way to solve this? As it's fairly easy to bruteforce.. If you are looking for a non-bruteforce way, add a 'no computers' tag to the question please. $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 10:51
  • 1
    $\begingroup$ Also, just to be clear: the 'beginning' state is unknown, and the every 'new' day starts with the end state after the last day? We assume students don't meddle with the lockers during the day? $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 10:55
  • $\begingroup$ Added the suggested edits. $\endgroup$
    – Mildwood
    Mar 21, 2016 at 11:01
  • $\begingroup$ I'm still struggling with what's really being asked here. Are you just looking for the odds for an alteration from 'all closed' to 'all open', or 'from any random state, to all open', or more general, asking for a function that describes the odds for day x, if you know that on day 0 all lockers were closed? $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 14:25
  • 1
    $\begingroup$ @MinusReputation, are you still around? I believe my solution is correct (and I believe none of the others is correctly reasoned, though some have arrived at the same answer as I have); if you agree, you might consider accepting my answer. (And if not, you might consider indicating what you find unsatisfactory about it.) $\endgroup$
    – Gareth McCaughan ♦
    May 11, 2016 at 16:34

6 Answers 6

Reset to default
6
$\begingroup$

Let S be the event we're interested in -- all the multiple-of-6 lockers ending up open. I'm gradually going to repeatedly make observations of the form "Pr(these lockers all end up open) = 1/2 Pr(all but one of these end up open)", supported each time by the fact that some particular coin-flip affects what happens to exactly one of these lockers.

(By "coin C affects locker L" here, I mean that the result of flipping coin C changes what happens to locker L. Note that this isn't the same as saying that locker L gets (or might get) opened/closed after flipping coin C; for instance, no coin "affects" the locker with the same number, in my terminology, because after flipping coin n you then always toggle the state of locker n because n is both a factor and a multiple of itself.)

Coin 13 affects locker 78 but no other multiple-of-6 locker. Therefore, S happens iff (S ignoring 78) happens and coin 13 comes out the right way. So Pr(S) = 1/2 Pr(S ignoring 78).

Coin 11 affects locker 66 but no other multiple-of-6 locker. So Pr(S ignoring 78) = 1/2 Pr(S ignoring 66,78).

Coin 32 affects locker 96 but no other multiple-of-6 locker. So Pr(S ignoring 66,78) = 1/2 Pr(S ignoring 66,78,96).

Coin 45 affects locker 90 but no other multiple-of-6 locker. So Pr(S ignoring 66,78,96) = 1/2 Pr(S ignoring 66,78,90,96).

Coin 27 affects locker 54 but no other multiple-of-6 locker. So Pr(S ignoring 66,78,90,96) = 1/2 Pr(S ignoring 54,66,78,90,96).

Coin 20 affects locker 60 but no other multiple-of-6 locker. So Pr(S ignoring 54.66.78.90,96) = 1/2 Pr(S ignoring 54,60,66,78,90,96).

Coin 15 affects locker 30 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 54,60,66,78,90,96) = 1/2 Pr(S ignoring 30,54,60,66,78,90,96).

Coin 78 affects locker 6 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 30,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,30,54,60,66,78,90,96).

Coin 60 affects locker 12 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,30,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,30,54,60,66,78,90,96).

Coin 54 affects locker 18 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,30,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,18,30,54,60,66,78,90,96).

Coin 84 affects locker 42 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,30,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,18,30,42,54,60,66,78,90,96).

Coin 48 affects locker 24 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,30,42,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,18,24,30,42,54,60,66,78,90,96).

Coin 96 affects locker 48 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,24,30,42,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,18,24,30,42,48,54,60,66,78,90,96).

Coin 24 affects locker 72 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,24,30,42,48,54,60,66,78,90,96) = 1/2 Pr(S ignoring 6,12,18,24,30,42,48,54,60,66,72,78,90,96).

Coin 72 affects locker 36 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,24,30,42,48,54,60,66,72,78,90,96) = 1/2 Pr(S ignoring 6,12,18,24,30,36,42,48,54,60,66,72,78,90,96).

Coin 42 affects locker 84 but no other multiple-of-6 locker not being ignored yet. So Pr(S ignoring 6,12,18,24,30,36,42,48,54,60,66,72,78,90,96) = 1/2 Pr(S ignoring 6,12,18,24,30,36,42,48,54,60,66,72,78,84,90,96).

And that's all the lockers. We introduced one factor of 1/2 for each of the 16 lockers, so the probability is 1/65536.

(Highbrow version: what we're doing here is solving a linear system of 16 equations over the finite field with 2 elements, and the above is reducing the system to upper-triangular form.)

Improve this answer
$\endgroup$
9
  • $\begingroup$ You are checking if a coin affects any other lockers. You're not checking if any other coins alter the state of the same locker though. There's a difference between checking if the state has been altered, and checking if it's been altered an odd number of times. The latter is required, while you only check the first (more lenient) condition. $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 15:36
  • $\begingroup$ Indeed I'm not checking if any other coins alter the same locker. I don't need to. The point is that, at each stage where I say "coin C affects locker L but no others we care about", no matter what the other coins do we have Pr(all these lockers open at end) = Pr(all open at end except maybe L) Pr(coin C comes out the right way to make sure L is open too), and the second factor is always 1/2. $\endgroup$
    – Gareth McCaughan ♦
    Mar 21, 2016 at 15:48
  • $\begingroup$ Still not quite sure if I fully agree. Tracking your progress, you state coin 84 only affects 42 and no others that aren't ignored already. At that point however, you still have 84 itself unaffected (see last step with coin 42). You can fix this by using coin 28 to eliminate 84 first, then use 84 to eliminate 42,.. just remove your final step then. Rather then taking that path, you can however go for this series to end up with a solution: 28 (to take out $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 16:28
  • $\begingroup$ Coin 84 doesn't affect locker 84, because 84 is both a factor of 84 and a multiple of 84 :-). $\endgroup$
    – Gareth McCaughan ♦
    Mar 21, 2016 at 16:30
  • $\begingroup$ Regardless of what the coin toss gives, it'll always change 84. If heads, state changes due to to it being a multiple, if tails, state changes due to it being a factor. It's not like it changes twice for both reasons (thus rendering a 'zero' operation) because it's head or tails, not both. Still wondering about it, and wondering if there's a path without such decisions. $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 16:36
9
$\begingroup$

Info for whoever wants to have a crack at this, I've listed all lockers with multiples of six (yellow) and all students that affect the position of any of those lockers (green), and how many lockers are affected by each relevant student. Turns out, out of 100 students, only 40 have a relevant role. enter image description here

Perhaps noteworthy: All lockers are affected by an even number of students.

NOTE: I've edited the table above: Impact from heads are 'x', impact from tails are the grey colored cells.

Improve this answer
$\endgroup$
0
3
$\begingroup$

Answer:

$$1/2^{16} = 1/65536$$

Explanation:

Let's call lockers which can be opened or closed by their number, so locker n Let's call the coin toss for each student by their number as well, either event n or coin toss n.

Consider locker n.

Without loss of generality, let's consider factors and multiples to be equivalent as far as locker n is concerned. Reasoning: whether a number k != n is a factor or a multiple of n, event k has a %50 chance to toggle the state of locker n and a %50 chance to not affect the state. (the event n has a %100 chance to toggle the state of locker n).

We will say that if k != n is a multiple or a factor of n, then event k is an affecting event of locker n

For a given locker, it has a %50 chance of being open and a %50 chance of being closed regardless of how many affecting events it has.

Base Case: Locker n has 1 affecting event. (actual example: it is a prime number > 50). After the affecting event occurs, locker n has equal chance of being closed or open. Then event n occurs, which simply toggles the state of locker n. So a locker n with 1 affecting event has a %50 chance of being closed, %50 chance of being open.

Inductive Case: Assume that for any locker with k affecting events, that it has a %50 chance of being open and a %50 chance of being closed. Now if we consider a locker with k+1 affecting events, after k affecting events have occurred, it has equal probability of being closed or open. the kth + 1 affecting event occurs and either leaves the locker in its current state or toggles the state of the locker. Either way, the locker still has equal probability of being open or closed.

Therefore, regardless of how many events (coin tosses) affect the state of the locker, any locker has a %50 chance of being open and %50 chance of being closed after all events have taken place.

So what is the probability that all lockers whose number is a multiple of 6 are open? There are 16 lockers that fit this criteria so the answer is $$1/2^{16} = 1/65536$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your induction is badly mistated. You are actually inducting on the state of a locker after $k$ events have taken place, not how many affecting events there are in total for the locker. But if you correct that, the actual reasoning is right. $\endgroup$
    – Paul Sinclair
    Mar 22, 2016 at 3:35
  • $\begingroup$ Let's suppose you've correctly proved that each locker has probability 1/2 of being open at the end. It doesn't follow that Pr(all 16 multiple-of-6 lockers are open at the end) is 1/2^16, because the lockers' events are not independent. Suppose e.g. we have two lockers and two students, and each student either opens both or closes both with probability 1/2. Then each locker has probability 1/2 of being open at the end, but Pr(both open at end) is 1/2, not 1/4. $\endgroup$
    – Gareth McCaughan ♦
    Mar 22, 2016 at 16:45
  • $\begingroup$ (That is not actually the structure we get in the question as posed with n=2, of course. But neither does the argument in this answer depend on the details of that structure.) Alternatively, suppose we do the same but start with one of the two lockers open and the other closed. Then again each locker is open at the end with probability 1/2, but now Pr(both open at end) is zero. $\endgroup$
    – Gareth McCaughan ♦
    Mar 22, 2016 at 16:47
2
$\begingroup$

Partial strategy, maybe someone can use it.

Notation:
13H - means the coin for student 13 ends up "head" (very tempted to say "student 13 gets ..." you know where this is going).
24T - means the coin for student 24 ends up "tail". (again, very tempted to say something else)
Let's start simple.

1H - then all the lockers multiple of 6 are opened. So $\frac{1}{2}$ chance.
1T + 2H. Again all 6M lockers are opened. So an additional $\frac{1}{4}$
1T + 2T + 3H. all 6M lockers are opened. So additional $\frac{1}{8}$
So from 3 students alone you get a chance of $\frac{7}{8}$

Got a bit stuck here, because obviously I cannot go through all the combinations, but I'm working on it.
Anyone willing to pitch in is welcomed.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Wouldn't that be 1/8 chance for all 6M lockers to be open? $\endgroup$
    – ASCIIThenANSI
    Mar 21, 2016 at 13:07
  • $\begingroup$ I feel like spamming ( ͡° ͜ʖ ͡°) all over your answers, but I will restrain. $\endgroup$
    – Mildwood
    Mar 21, 2016 at 13:08
  • $\begingroup$ @MinusReputation. Why is that? Please tell me what I did wrong so I won't do it again. $\endgroup$
    – Marius
    Mar 21, 2016 at 13:13
  • 1
    $\begingroup$ @Marius: Based on your comment, I'd like to point out the end state of a loop (the series of all students) is to be evaluated. You can only count as 'valid' the situations where after all students have cycled, the condition is met. Conditions met somewhere along the way, but not in the end state, is not valid. $\endgroup$
    – Tim Couwelier
    Mar 21, 2016 at 14:45
  • 1
    $\begingroup$ @Marius I think MinusReputation was thinking along the lines of "gets heads" and "gets tails" with the obvious sexual connotation. So he would spam his little ascii dude everywhere to make the connection more obvious and obscene. $\endgroup$
    – Trenin
    Mar 21, 2016 at 14:52
0
$\begingroup$

The answer is:

1 / 2 ^ 16 = 1 / 65536

The reasoning is:

For all lockers to be open, the student owning the locker has to flip heads. Otherwise, the locker will close and there will be no multiples left to open it.
The probability of landing a heads is 1 / 2.
But for the locker to stay open, every other student must not land tails and close it.
For example, Student 6 opens their locker, and Students 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, and 96 can't land tails for the locker to stay open.
But, if all those students land heads, then all the lockers with a multiple of 6 MUST be open, because there's no-one else to close them. There are 16 students with multiples of 6, and each one has a 1 / 2 probability of getting a heads.
(1 / 2) ^ 16 = 1 / 65536.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But any number is a factor and a multiple of itself; every student will toggle their own locker on a heads or a tails $\endgroup$
    – LowIntHighCha
    Mar 21, 2016 at 12:43
  • $\begingroup$ @LogicianWithAHat Didn't realize it wasn't a toggle. $\endgroup$
    – ASCIIThenANSI
    Mar 21, 2016 at 13:06
0
$\begingroup$

1/2^16

Consider an arbitrary locker n.
Suppose it has probability p of being open when the nth student flips.

After the nth student flips, the locker has a probability .5*p (tails, already open) + .5*(1-p) (heads, previously closed) =.5 of being open.

After the nth student flips, the locker remains unchanged- so each locker has a .5 chance of being open after all flips.

As there are 16 relevant lockers, the total probability is 1/2^16

Improve this answer
$\endgroup$
2
  • $\begingroup$ Your description does not match what the puzzle says at all. Student $n$ will always change the state of the locker, regardless of what they flip and what state the locker is already in, and higher numbered students may change the state of the locker, when $n$ divides their own number. $\endgroup$
    – Paul Sinclair
    Mar 22, 2016 at 3:25
  • $\begingroup$ You are correct, I did not read carefully enough. Theory my still hold, but it's much less clear $\endgroup$
    – Monkooky
    Mar 22, 2016 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.