20
$\begingroup$

A prison warden offers his inmates a game for their freedom. He will secretly write a number on each of their foreheads, with no two foreheads having the same number. The inmates get to look around, seeing every other inmates' forehead, but not their own. They then go into separate rooms, and each place either a white or black hat on their own head. When they return, the prisoners are lined up in order of forehead number. They win if their hat colors now alternate white/black.

Once the game begins, the prisoners may not communicate, but beforehand, they may agree on a strategy. How can they guarantee victory?

This puzzle has a logical solution, there is no need for lateral thinking.

Added remarks: The numbers aren't necessarily integers, or positive, or interrelated at all (except they are all different). The numbers are the wardens choices, while the hat colors are the prisoners' choice. I got this from Rustan Leino's puzzle page.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Are the numbers consecutive, integers, positive? $\endgroup$
    – leoll2
    Apr 8, 2015 at 17:02
  • 1
    $\begingroup$ some questions 1) are the numbers consecutive, like 1,2,3,4 or it's random? 2) Number of white hats always equals to number of black hats +/- 1? $\endgroup$
    – Alex
    Apr 8, 2015 at 17:04
  • 2
    $\begingroup$ @Alex I think that each inmate has a white hat and a black hat and they have to choose which to put on. $\endgroup$
    – Rob Watts
    Apr 8, 2015 at 17:07
  • 1
    $\begingroup$ @leoll2: Not quite. It translates into "given a sequence of numbers, determine whether you're in an odd or even position relative to that sequence." $\endgroup$
    – user88
    Apr 8, 2015 at 17:57
  • 1
    $\begingroup$ @JoeZ. It doesn't translate to determining any information about your position relative to a given sequence. $\endgroup$
    – h34
    Apr 8, 2015 at 18:40

2 Answers 2

Reset to default
19
$\begingroup$

Before the "game", the prisoners decide on this strategy:

Assign an integer 1, 2, ..., n to each prisoner arbitrarily and call this the "prisoner number". When the numbers are shown, each prisoner determines how many swaps (swapping adjacent prisoners) it would take to change the others from "forehead order" to "prisoner order". If it takes an even number of swaps, the odd prisoners (1,3,5...) wear a white hat and the evens a black one. If it's odd, they wear the opposite hat.

For example, take three prisoners 1,2,3. The only possible "forehead orderings" are:

123    1 sees 23(W)    2 sees 13(B)    3 sees 12(W)
132    1 sees 32(B)    3 sees 12(W)    2 sees 13(B)
231    2 sees 31(W)    3 sees 21(B)    1 sees 23(W)
213    2 sees 13(B)    1 sees 23(W)    3 sees 21(B)
312    3 sees 12(W)    1 sees 32(B)    2 sees 31(W)
321    3 sees 21(B)    2 sees 31(W)    1 sees 32(B)

While three prisoners allows only one swap maximum, it illustrates the point (I really don't want to do a larger table...). This generalizes to more prisoners, and just means they just need to figure out if the forehead order they see is an even or odd permutation of the prisoner order.

Improve this answer
$\endgroup$
16
  • $\begingroup$ This was what I was trying to do originally, but couldn't figure out how to express it. I think this is the correct solution. $\endgroup$
    – user88
    Apr 8, 2015 at 18:03
  • $\begingroup$ It could use a more rigorous statement than (this generalizes to more...) for sure, but I'm not sure how to go about putting it into words. $\endgroup$
    – Set Big O
    Apr 8, 2015 at 18:05
  • $\begingroup$ This is EXACTLY the answer I came up with and was just about to post. $\endgroup$
    – Taylor Brandstetter
    Apr 8, 2015 at 18:05
  • 1
    $\begingroup$ Doesn't the warden choose numbers randomly? (i.e. forehead numbers could be sqrt(2), 1.741, -27, etc) How does this work in that case? Am I not understanding the strategy? "The numbers aren't necessarily integers, or positive, or interrelated at all (except they are all different)." $\endgroup$
    – nanofarad
    Apr 8, 2015 at 23:14
  • 8
    $\begingroup$ While correct, I feel like this answer leaves out the elegant proof that the solution works: 1) It (obviously) works if the warden's ordering matches the prisoner's chosen ordering; 2) If it works for one choice of warden's ordering, it works if you start with that ordering and swap two prisoners, since doing so will cause all the prisoners except those swapped to switch the color hat they choose; 3) You can get from any ordering to any other ordering via a sequence of swaps. $\endgroup$
    – Dan Staley
    Apr 8, 2015 at 23:26
0
$\begingroup$

They achieve the goal as follows:

They decide that all of their number except two must be killed, and once they have accomplished that grisly task the tallest survivor wears white and the other prisoner wears black.

Improve this answer
$\endgroup$
5
  • $\begingroup$ There is no "Lateral Thinking" tag on this post... $\endgroup$
    – Engineer Toast
    Apr 8, 2015 at 18:15
  • $\begingroup$ That's a nice backup plan if they don't know permutations. $\endgroup$
    – Ben Frankel
    Apr 8, 2015 at 18:16
  • $\begingroup$ And then get sent back to prison for murder. Smart ;) $\endgroup$
    – Set Big O
    Apr 8, 2015 at 18:20
  • $\begingroup$ @Geobits - Why not self-sacrifice? $\endgroup$
    – h34
    Apr 8, 2015 at 18:28
  • $\begingroup$ I guess that's possible, but I'm not sure the cops would buy it... $\endgroup$
    – Set Big O
    Apr 8, 2015 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.