Hats, Hats, And Hats Some More

Time for a new problem I suppose. This one is going to be a bit weird, because as I understand it part of this is actually an open problem. The solution is only known in a few special cases, and so part of the problem will be to find how those cases fit in. Here we go:

There are N people in a room, each of them wearing hats. The hats can either be white or black, and standard hat rules will apply. At a specified time, each person simultaneously must either guess their own hat colour or pass. The players win the game if nobody guessed their hat colour incorrectly and somebody guessed correctly. They lose the game if either somebody was wrong, or everybody passed. The players are free to strategize before the hats are assigned. Find a strategy for the N player case such that in the limit as N goes to infinity, the probability of success goes to 1.

This problem as it is stated can be solved, its not an open problem really. Solving it in the N person case optimally is an open problem, so don't worry about that.

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".

Hints In A Room

So as a follow-up to my hats in a room puzzle, I'm going to be doing something unusual this time....I'm going to be giving a hint. This puzzle is particularly difficult, and even with this hint it still is quite a trick. Before giving the hint though, lets go through some of the logic that you have probably already gone through.

First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2¹⁰⁰). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(₁₀₀C₅₀) chance of success. This is substantially better than 1/(2¹⁰⁰), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.

The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.

I'll finish the entire solution some time later this week.

Hats In A Room

So, I haven't been in town for a while, I've been away at the go congress. My performance there was average, but I'm happy with the games I played. Anyway, onto the new puzzle. I first learned this one from Bart:

There are 100 prisoners in a room (we shall call this room A) and the warden of these prisoners has decided to play a game with them. In another room (room B) there are 100 hats, and each one has the name of one of the prisoners underneath it (each prisoner has a unique name). A prisoner will be selected randomly and sent into room B. While in room B, the prisoner may look underneath 50 of the hats and then will be sent into another room (room C). Room B will then be restored to its initial state before a new prisoner is sent into it.

One by one, each prisoner will have a chance to look underneath 50 hats before being sent into room C. Once they are all in room C, they will all be released if each one of them has looked under the hat that contains their own name. If any of them has not looked under the hat that contains their own name, they will be sent to their cells for another night and the scenario will be run again tomorrow, with the names randomized underneath the hats each time.

The prisoners may plan while in room A. Come up with a strategy that, on average, will set them free in less than a week.

As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".