The Lowest One

Solution time! Last puzzle was about Infinite Hats. Actually, its funny, I found a solution and then I told it to Mark and he found a slightly different solution that had the exact same probability of working, but then those clever people over at Tanya Khovanova’s Math Blog found a better solution than mine. Anyway, lets go over my solution first, because I'm egotistical like that.

First lets consider the two person case, as soon a one person guesses we are at probability 1/2 of being correct, and we simply need to make sure that both of them are right together or that they are wrong together. Specifically, I want to make sure that if Alice guesses wrong, Bob will also guess wrong (say). In this case, suppose Alice looks at Bobs hats and writes down the smallest number that is a black hat and similarly Bob writes down the lowest number that is a black hat on Alices head. So if Bobs first hat is black, Alice will write down 1 and then if she is wrong Bob will also be wrong.

What is the actual chance of this working? We will calculate this by looking up the hats on their heads slowly, starting at the bottom. If both are black then we lose, if one is white while the other is black, then the person with a white hat is considered correct, and if both are white we move up to the next pair of hats. Let P be the chance that one person is correct, in this case we have
P=0*1/4+1*1/4+1*1/4+P*1/4

that is, 1/4 of the time we get BB and we are wrong, in the cases where we get BW or WB then we are get one person correct, and in the case of WW we haven't really changed anything. One can solve this to get P=2/3.

Now that one person is correct, what is the chance that the other person is correct? Suppose we have already seen WB go by, so person 1 is already correct, now WB and WW both have no effect, and BB results in a loss while BW results in a win. This the odds are 1/2 of the second person being correct. All in all, the probability is 1/3 of winning the game, better than 1/4.

Actually, there is a faster way to arrive at that answer of 1/3. Consider looking at the hats that occur, from the bottom up, you will see a series of things like WW, WB, BW, BB, and then look for the lowest occurrence of each of BW, WB, and BB. If BW and WB each occur before BB, then we win. That is, of those three if the highest is BB then we win, which is clearly 1/3.

Naturally this strategy generalizes to 100 quite easily. Simply look for the lowest occurrence of all black hats by your teammates and write down that number. The relevant sequences are BBB...BBW, BBB...BWB, BBB...BWBB, ...., BWBB...BB, WBB...BBB, and BBB...BBB, of which there are 101. There is a 1/101 chance that the last one is that all black one, and then we win. This generalizes to a strategy that works with probability 1/(N+1).

Marks strategy was slightly different, instead writing down the lowest occurrence of all white hats rather than all black hats (attempting the align when the players are right rather than when they are wrong). The relevant sequences are the all white and all white with one black, again N+1 of them in total. Naturally the game is won if all white occurs before any of the other ones, and that is again 1/(N+1).

The better strategy can be arrived at in a similar fashion to some other hat puzzles, using modular arithmetic. First, let Ki be the location of the lowest white hat on person i's head. Let S be the sum of all the Ki. If each person knew S, they could find the value of Ki. Fix a constant CN (the constant can depend on N, the number of players). Each person is to make their guess assuming the following two things:
1) S mod CN = 0
2) each Ki is no larger than CN

If these statements are actually true, then this is enough for the players to guess correctly. What is the chance that those two statements were actually correct? Well, the largest Ki is going to be about as large as lg(N) (lg being log base 2), so if CN - lg(N) gets large as N goes to infinity, we should be safe as far as the second point is concerned. As for the first one, it will be on average probability 1/CN, since S is just a random number, and the two points are approximately independent. For example you could use CN=2lg(N) and then you have a chance of winning of about 1/2lg(N), maybe a little worse, but this is asymptotically much better than 1/(N+1). One of the posters at Tanya Khovanova's Blog showed that it is basically optimal to use CN=lg(N)+lg(lg(N))-lg(lg(lg(N))), but thats neither here nor there.

It is interesting that this better solution always attempts to find the location of the lowest white hat on your head, rather than any hat at all, so it seems clear one should be able to do better than this, but it is not clear how much better.

No comments: