Problem of the Week 1179

An Infinitely Puzzling Hat Problem

Alice, Bob, Charlie, and Diane are prisoners of warden Waldo, who announces that at a certain time he will place infinitely many numbered white or black hats on the heads of each of them; each will have hat #1, hat #2, and so on and colors are chosen randomly with probability 1/2. Each person will see all the colored hats, except those on his or her head.

When Waldo gives the signal, each prisoner will write down a number; this choice is simultaneous, and they need not choose the same numbers. Waldo will check the color of each speaker's hat corresponding to his or her chosen number. If all four chosen colors are black, all prisoners are freed. If not, they stay in prison until Waldo devises a new hat puzzle.

The prisoners can plan a strategy before the event, but cannot communicate after the hats are placed. If they each just guess, say, 1179, then their probability of success is 1/16. Find a better strategy.

The interesting problem here is the case of n people, n ≥ 2. I used n = 4 because it illustrates many subtle points of the problem (and I just found a nice strategy for this case, and will be impressed if you find one as good).

Source: The problem is due to Lionel Levine (2011); I heard it from Joe Buhler. It is a very rich problem. More source details will be posted with the solution.

© Copyright 2014 Stan Wagon. Reproduced with permission.

[View the solution]