23

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.

Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • 1
    Are the numbers consecutive, integers, positive? – leoll2 Apr 08 '15 at 17:02
  • 1
    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? – Alex Apr 08 '15 at 17:04
  • 2
    @Alex I think that each inmate has a white hat and a black hat and they have to choose which to put on. – Rob Watts Apr 08 '15 at 17:07
  • @RobWatts Oh so that's part of the game, not the setup of the game, i see thanks. – Alex Apr 08 '15 at 17:08
  • I'm very curious to see the answer of this problem, as "the prisoners may not communicate" translates the problem into: given a sequence of numbers, determine what number (you) is missing in that sequence. Probably I'm missing some information, let's see... – leoll2 Apr 08 '15 at 17:14
  • @Alex the numbers could be finite decimals, and need not be positive. They are "random", or rather, not chosen by any rule other than the warden's whims. As for the hats, imagine the private rooms they each enter have one hat of each color, and the prisoner chooses which one to put on – Mike Earnest Apr 08 '15 at 17:17
  • 1
    @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." –  Apr 08 '15 at 17:57
  • 1
    @JoeZ. It doesn't translate to determining any information about your position relative to a given sequence. – h34 Apr 08 '15 at 18:40

2 Answers2

20

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.

Duncan
  • 5,045
  • 24
  • 28
Set Big O
  • 6,604
  • 3
  • 28
  • 41
  • 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. –  Apr 08 '15 at 18:03
  • 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. – Set Big O Apr 08 '15 at 18:05
  • This is EXACTLY the answer I came up with and was just about to post. – Taylor Brandstetter Apr 08 '15 at 18:05
  • I'm sure this is the correct answer, and it's very neat, but in practice if there were say 10 or more prisoners then I think even if they were all maths graduates there would often be at least one who got the parity of the number of permutations wrong, just out of human error in the circumstances. What's the neatest way of calculating that parity? – h34 Apr 08 '15 at 18:26
  • @h34 In reality, sure, any large group of prisoners is dead. I think it's a standard assumption in these puzzles that a) the warden is a sadistic lunatic, but more importantly b) all prisoners are human calculators. – Set Big O Apr 08 '15 at 18:29
  • The prisoners are provided pen and paper and time proportional to the complexity of computing the parity of a permutation on $n$ prisoners. – Ben Frankel Apr 08 '15 at 18:30
  • @BenFrankel: If the prisoners know how to do bubble sort, it's only $O(n^2)$. –  Apr 08 '15 at 18:34
  • @JoeZ. Oh right, they just have to sort the permutation and keep track of how many swaps they've done (or at least the parity of such). It would be $O(n\log(n))$ then, though they may have to spend some more time coming up with a sorting algorithm while they're coming up with a strategy. – Ben Frankel Apr 08 '15 at 18:40
  • @BenFrankel The $O(n^2)$ algorithms are generally easier for humans to do. –  Apr 08 '15 at 18:42
  • 1
    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)." – nanofarad Apr 08 '15 at 23:14
  • 8
    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. – Dan Staley Apr 08 '15 at 23:26
  • @hexafraction It's only the order of the numbers that's important to this solution, so any set of unique numbers will do so long as every of those numbers can be considered larger or smaller than all the rest. (For example, they're in trouble if the warden uses general complex numbers - it won't work with 3 prisoners having 0, $i$, 1 since the prisoner with 0 won't be able to say $i > 1$ or $i < 1$.) – Lawrence Apr 08 '15 at 23:56
  • @DanStaley That's what I meant in my first comment, but I just couldn't figure out a simple, intuitive way to say it. Please feel free to edit it into the answer if you think that improves it (I do). – Set Big O Apr 09 '15 at 12:41
  • Can we get the solution/explanation in spoilers, please? – Carl Feb 29 '16 at 03:23
  • @Carl The solution and explanation make up the whole answer, and I disagree with putting an entire answer in spoiler blocks. – Set Big O Feb 29 '16 at 04:26
  • I understood the method but couldn't understand the intuition behind it . Can someone please explain why this method gives the correct answer ? – Hemant Agarwal May 31 '20 at 08:21
-1

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.

h34
  • 4,569
  • 2
  • 20
  • 42