Another classic: N prisoners, each with a black or white hat, chosen uniformly and independently. When a bell rings (and it only rings once) each either guesses the color of their own hat or remains silent. If no one speaks, they all die; if _anyone_ guesses their hat color wrong, they all die; but if at least one person guesses their own hat correctly, and no one guesses incorrectly, they all live. Note that whenever someone speaks, they are correct with probability 1/2. Nevertheless, show that (with some planning beforehand) the prisoners can win with probability approaching 1 as N -> infinity. This got some nice press: http://www.nytimes.com/2001/04/10/science/why-mathematicians-now-care-about-... - Cris On Apr 16, 2015, at 8:40 AM, Veit Elser <ve10@cornell.edu> wrote:
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).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun