# Alternating Hat Colors

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.

• Are the numbers consecutive, integers, positive? – leoll2 Apr 8 '15 at 17:02
• 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 8 '15 at 17:04
• @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 8 '15 at 17:07
• @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." – Joe Z. Apr 8 '15 at 17:57
• @JoeZ. It doesn't translate to determining any information about your position relative to a given sequence. – h34 Apr 8 '15 at 18:40

## 2 Answers

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.

• 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. – Joe Z. Apr 8 '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 8 '15 at 18:05
• This is EXACTLY the answer I came up with and was just about to post. – Taylor Brandstetter Apr 8 '15 at 18:05
• 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)." – hexafraction Apr 8 '15 at 23:14
• 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 8 '15 at 23:26

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.

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