And We All Go Down Together

OK, I feel like distracting myself from work, so its time to post the full solution to the hats in a room puzzle. You must have already seen the hint I gave, so I will go from there.

The next case to solve is the four person case. The random strategy for that case gives a 1/16 chance of success, and the 'left-right' strategy gives 1/6. Doesn't seem like there is much room to improve, but lets try. First, let us name our people Adam, Betty, Candy, and Dale (I suppose I could give them numbers as names, but the hats will also need to be numbered, and it will make my explanation a bit less transparent). Suppose we plan to have Adam and Betty look under the two hats on the left, and Candy and Dale will look under the two hats to the right. Adam will look under hat 1 first, if he sees his own name, then all is well. If he sees Betty's name in that hat, then we are still OK. However, if he sees either Candy or Dale under that hat, then there is a problem.

If Adam knows that Candy's name is under hat 1, then he knows that the plan is going to fail unless he aborts. Whats more, he knows that the plan will fail anyway unless Candy also aborted. One way that Candy will abort is if she sees Adam's name under hat 3. If Candy sees Adam's name under hat 3, she will know that the default plan is doomed, and must abort. Thus, if Adam sees Candy's name under hat 1, he should look under hat 3 next. Out of some sort of symmetry, he might as well look under hat 4 if he sees Dale's name under hat 1.

At this point you can guess the strategy (actually, lots of people guess this strategy after the hint, but few are able to convince themselves it actually works). Adam will be assigned hat 1, Betty hat 2, Candy hat 3, and Dale hat 4. Look under your own hat, and whatever name you see, look under that persons hat next. What are the odds this works? Its is easy enough just to look at all 24 arrangements of the hats and see. I will denote an arrangement like Adam under hat 1, Dale under hat 2, Candy under hat 3, Betty under hat 4, with the letter sequence ADCB, and write S for success and F for fail.

ABCD - S
ABDC - S
ACBD - S
ACDB - F
ADBC - F
ADCB - S
BACD - S
BADC - S
BCAD - F
BCDA - F
BDAC - F
BDCA - F
CABD - F
CADB - F
CBAD - S
CBDA - F
CDAB - S
CDBA - F
DABC - F
DACB - F
DBAC - F
DBCA - S
DCAB - F
DCBA - S

So, 10 successes out of 24, thats better than the 'left-right' strategy of 6 successes out of 24 (actually, those successes are a subset of these ones). Okay, its not likely that we will do better than that, as its easy to show that no matter what the first person does, he cannot win with more than 1/2 chance, so at best we can approach 12 out of 24. Back to the 100 person case.

With 100 people the strategy generalizes simply, assign each of them a number and have each person look under the hat of their number. Then go to the hat corresponding to the name of the person you saw under that hat, repeat until you either see your own name or you have looked at 50 hats. There is no concern that you get sent back to your first hat, as only seeing your own name can do that.

Easy enough strategy, does it work? More simply, given the numbers 1 to 100 in a line (an element of the permutation group) what are the odds that there is no cycle of length 51 or more?

Alright, we know that in total there are 100! ways to arrange the numbers 1 to 100, how many of them contain a cycle of length 51 or more? Well, lets assume we wanted to construct a list with a cycle of length n (with n>50), then there are ₁₀₀C_n ways to choose those elements. Given those n elements to form a cycle, there are (n-1)! ways to arrange them into a cycle (because the first one can link to n-1 others, the second one to n-2 others and so on). Finally the remaining 100-n elements can be arranged (100-n)! ways (note there is no concern of the remaining elements forming a cycle of length n, as n>50).

We can see that the total number of ways to create a list of the numbers 1 to 100 that contains a cycle of length exactly n is:

T(n)=₁₀₀C_n*(n-1)!*(100-n)!
=100!*(n-1)!*(100-n)!/(n!(100-n)!)
=100!/n

Well, isn't that nice.

So the probability that there is a cycle of length n is

Σ T(n)/100!

Where the sum has n going from 51 to 100. The sum can easily be calculated on some math program, or you can approximate is as an integral if you believe that 100 is large enough (it is). Then it is the integral from y to 2y of 1/x dx, which is simply ln(2)≈ 0.69. That is the total probability of failure.

We can see that even in the case that the number of prisoners tends to infinity, the chance of success using this strategy will, at worst, be 1-ln(2)≈ 0.31. Thus they can expect to get out in just over 3 days.

As a side note, what are the odds that the first person expects to find his name when he first enters the room? He will not find his name if it is part of a cycle of length n with n>50. There are ₉₉C_n-1 ways to choose the other n-1 elements, and (n-1)! ways to arrange them into a cycle, and (100-n)! ways to arrange the remaining elements. Thus, we are interested in summing

₉₉C_n-1*(n-1)!*(100-n)!/100!

as n goes from 51 to 100. But that term is exactly 1/100, so after summing we will have 1/2.

As one would expect, the chance of the first person (or any individual, for that matter) finding their own name is 1/2. However, if that person is wrong, then there are at least 50 other people who are wrong with them. This is standard in problems where one person being wrong ruins everything. Make sure that nobody is ever wrong alone, they must take as many people with them as possible.

On the other hand, with problems where you only need one person to be right (such as with some of my earlier hat problems), you need to make sure they are always right alone, so you don't waste any extra "rightness".