Tanya Khovanova's Math Blog, in a 2010 posting, attributes the puzzle to Leonid Makar-Limanov. Another excellent example of this kind of puzzle is Lionel Levine’s hats puzzle*. Sometimes the warden is a sultan and the prisoners are his wizards. In any case, the premise is that the protagonists manage to transmit information in seemingly impossible circumstances. * N prisoners are in a room. Each is wearing an infinite tower of hats of two colors, black and white. The hats were placed on each prisoner by the warden, who chose the sequence of colors on each head by flipping a fair coin. The hat towers are visible to each prisoner, except of course a prisoner cannot see his own tower. Before all this happened, the prisoners were allowed to have a strategy session and communicate freely. In the hat room, however, all communication is forbidden. There, each prisoner is only able to examine the hats on all the other prisoners. After the prisoners have had a chance to do this, they all must write down a likely position (1 or 2 or 3 etc.) of a black hat in their own tower. The scoring for this game is very simple. If all N prisoners correctly locate a black hat they are all released from prison. But if even one prisoner gives the position of a white hat, then all are given a life sentence. Do the prisoners have a strategy that improves the probability they are released (over just random guesses), and if so, what is the best strategy?
On Apr 15, 2015, at 1:25 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
This puzzle, and related ones, seem to be coming up a lot. It was performed (with 16 replacing 64) at a recreational math conference I recently attended in Portugal earlier this year. I was also told about it at the last Gathering 4 Gardner in Atlanta (spring 2014). The person who showed it to me first was Colin Wright I think (cc'ed), who might be able to say where he heard about it (if he didn't make it up himself).