Using your Head is Permitted

September 2010 riddle

The following riddle comes from Oded Margalit, who heard it from Noga Alon. (It has had previous publications, so if you have any prior familiarity with it, please do not send in a solution.)

A hundred prisoners are gathered together by their warden. Each prisoner gets two gloves: one black and one white. They are told that they have one night in order to plan a strategy, after which no communication between them will be possible. In the morning, they are told, each prisoner will have a distinct real number painted on his forehead. Each prisoner will be able to see the numbers painted on all other prisoners, but not his own. What each prisoner needs to do is to decide which glove to put on which hand. Once all prisoners have donned all gloves, they will be placed in a long line, one beside the other, ordered according to the value of the number on their foreheads, and will be asked to hold hands. If the pairs of hands holding each other all have same-colored gloves, all 100 prisoners will be set free.

Your goal is to design a strategy that will maximize the probability of this happening.

List of solvers:

Jim Boyce (2 September 13:11)
Jan Fricke (3 September 01:17)
Naftali Peles (5 September 07:02)
Daniel Bitin (7 September 01:55)
Sen Gu (8 September 21:38)
Lewei Weng (9 September 12:03)
Adam Daire (11 September 05:17)
Phil Hu (14 September 01:39)
Guangda Huzhang (14 September 17:18)
Omer Angel (15 September 10:07)
Hongcheng Zhu (18 September 18:10)
Song Lin (21 September 12:55)
Itsik Horovitz (24 September 23:32)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page