A classic maths puzzle involves a line of one hundred prisoners, who have each been given a black or white hat by their nefarious captor, and must each correctly shout out the colour of their hat to win freedom. The twist is that the prisoners don’t know the colour of their own hat, and though they can see the colours of the hats in front of them, they don’t know many of each colour there are overall. They can confer on a strategy beforehand, and the aim is to get as many of them to correctly identify their hat colour as possible. You can find a full explanation here (and in many other places!)

There are several ‘sequels’ to this puzzle, some involving an infinite number of prisoners and requiring the axiom of choice to solve. This post is about a nice variation on the theme that I heard about at a recent MathsJam. It can (just about) be solved without knowledge of higher mathematics, and though it seems impossible at first glance, the prisoners in this situation can in fact save themselves with 100% certainty.

The Puzzle

Ten prisoners are in a room together. Their captor writes a number on each of their foreheads (with no conditions on what the numbers might be except that they are all different real numbers). Each prisoner may look at the numbers on the others’ foreheads but can’t see their own number — there are no reflective surfaces. Prisoners aren’t allowed any communication of any type once they have been given numbers. After some length of time (enough to look at everyone else’s number and perform whatever calculations they consider necessary) they are each led to a different isolated dressing room and must don either a black or a white hat. The prisoners then return to the main room, and are arranged in order of the numbers on their foreheads. The prisoners win and are freed if the colours of their hats alternates along the line. The prisoners lose and are executed (or lose but are freed anyway, depending on your sensibilities) if the colours do not strictly alternate.

Before they are given numbers, the prisoners are told the rules of the puzzle, and may confer and determine a strategy, working as a team. Is there a strategy they can find that will guarantee them victory?

WARNING

As with all puzzles of this type, you should definitely try it yourself before reading any of the discussion below. Also, a disclaimer: I came up with the following solution (mostly) myself. I believe it is correct and essentially the only possible solution, but I have made no attempt to look up any published answer. If you think this solution is wrong or can be reformulated in a simpler way, please do let me know.

Analysis

On the face of it, the prisoners’ task seems impossible. Each prisoner can see the other nine prisoners’ numbers, so knows the order they will stand in. But crucially, they don’t know where they themselves will slot in, being unable to see their own number. Yet from this apparently insufficient information, and being unable to communicate with each other after they’ve been provided with this scarce amount of data, they must somehow co-operate and select one of only two correct choices of ten hats, out of 2^{10}=1,024 possiblilites.

Yet clearly the puzzle has a solution or else you would not be reading this. So how can the solution work? Let’s begin by looking at a simplified version of the problem.

The three-prisoner case

As a simple example, we consider the case where there are only three prisoners (the puzzle is exactly the same as described except with the word `ten’ replaced with `three’). We shall call the prisoners A, B and C. So each prisoner can see the two other prisoners’ numbers but not their own. Since the captor has free choice of numbers, it should be clear that nothing can be inferred from the actual values of the numbers, only whether they are larger or smaller than each other, since this is what determines the order they will be arranged in at the end. For instance, suppose A observes that B has the number 165.33 and C has 165.34. Prisoner A cannot deduce that he is `unlikely’ to have a number between 165.33 and 165.34 because they are close together — the captor may have chosen three nearby numbers to confuse the prisoners and A may have the number 165.335. At any rate, we are after a solution that is guaranteedto work, not merely likely to. So each prisoner has one piece of information to act on (literally, one `bit’ of data): which of the other two prisoners has the higher number. So we have a limited number of possible strategies to choose from, and playing with different possibilities you may alight on the following winning strategy:

• A dons a white hat if B<C and a black hat otherwise.
• B dons a black hat if A<C and a white hat otherwise.
• C dons a white hat if A<B and a black hat otherwise.

(Note that here we use the obvious notation `X<Y’ to mean `X has a higher number written on their forehead than Y’.)

We can show that this strategy works in all cases by constructing the following table:

Here the `arrangement’ column gives the final order that the prisoners will stand in as determined by their numbers. The columns for each prisoner show the information that they can see, and the hat they should choose according to the strategy. The `results’ column shows the final arrangement of hats the prisoners select. We can see that for any of the six possible arrangements of the prisoners, if each dons the hat specified by the rules above based on what they can see, they will successfully form an alternating line of colours. In fact, it is possible to derive this strategy from first principles. To start with, let’s suppose that our prisoners’ strategy will result in them standing º•º in the case where A has the smallest number and C the largest. So the first row of our table will look the same as above. But then we can also fill in the parts of the rest of the table where prisoners see the same thing as in this case, since seeing the same thing must lead to the same choice of hat. So far, we have developed the incomplete strategy:

• A dons a white hat if B<C and we don’t know what otherwise.
• B dons a black hat if A<C and we don’t know what otherwise.

And we can expand our strategy table this far:

Since rows 2–5 each have at least one prisoner’s hat specified, we know what the assignments have to be for the empty cells to create alternating rows of hats in the results column. So we could fill in the gaps in these rows — for instance, we know that in the A-C-B arrangement, A will see C<B and will end up stood next to C in a white hat. So when A sees C<B he must don a black hat. These filled in cells tell us what to do in the three cases missing from our strategy. So now we have developed an entire strategy, and we can fill in the last row of the table, verifying that the strategy works in all cases. This also shows that the given strategy is unique — apart from the strategy identical to this but with black and white swapped — since everything followed from the necessary assumption that the strategy must result in alternating hats for the A-B-C row.

Building a strategy for the four-prisoner case

Now suppose there are four prisoners instead of three. Here things are more complicated. The forehead numbers can give rise to 24 possible arrangements of the prisoners. Also, instead of each prisoner being able to see two other numbers, so that simply one is bigger or smaller than the other, he can see one of six possible `sub-arrangements’ of three numbers. For example, prisoner B might see that the other three prisoners are in the order A-C-D, A-D-C, C-A-D, C-D-A, D-A-C or D-C-A. A strategy needs to assign each of the four prisoners a hat for each of the six sub-arrangements he might see.

Although the equivalent table to the one we constructed for three prisoners would have 24 rows and 6 columns to fill in, we could go through the same process, beginning with enough parts of the strategy determined to get A-B-C-D right, feeding this into the table, filling in the necessary boxes to make partially completed rows work, putting the new instructions into the strategy, and repeating the process until the strategy and the results table are full. Starting with the A-B-C-D arrangement as º•º•, we would get the strategy summarised in the following table:

This is all very well, but following the same procedure for the original 10-prisoner puzzle — where the results table has 3,628,800 rows and 362,880 columns — is obviously a non-starter. But perhaps we can get some ideas from looking at the four-prisoner strategy regarding how it might generalise.

Generalising the four-prisoner strategy

You’ll notice from brief glance at the four-prisoner strategy table that A and C have identical strategies (note that the columns in the table are arranged in the same logical order for both rows — it’s in fact just the sub-arrangements put into alphabetical order). And prisoners B and D have the same strategy as each other, which moreover is the exact opposite of A and C’s strategy. So why does this strategy work, and how does it generalise to more than four prisoners?

Notice that prisoner A, who wears a white hat when he sees the `standard’ sub-arrangement B-C-D, wears black when he sees sub-arrangements where one of these letters is in the same place and two have swapped, and wears a white hat when all three have cycled round. Prisoners B, C and D follow similar rules. Why might this be? Let’s look at a couple of arrangements to see.

We began by building a strategy that works for the arrangement A-B-C-D. But what happens if we change the arrangement slightly to B-A-C-D? We see that having swapped A and B, they both still see the same thing: A still sees B-C-D and B still sees A-C-D. So they will wear the same hats as for A-B-C-D. But, they have swapped position. So instead of º•º•, our result will look like •º??. This means C needs to wear black and D white, the opposite of what they wear for A-B-C-D. The same principle applies for any two adjacent prisoners swapping, and for any number of prisoners. We can now start to develop a general strategy for any number of players:

• If a prisoner sees a sub-arrangement with all the other prisoners in alphabetical order then:
• • If he is prisoner A,C,E,…, he wears white.
  • If he is prisoner B,D,F,… he wears black.

If a prisoner sees a sub-arrangement different from alphabetical order just by one swap of adjacent-lettered prisoners, wear the other hat to the one stated in rule 1.

Rule 1 ensures the prisoners wear the correct hats when the forehead numbers arrange them in alphabetical order A-B-C-D-…, while rule 2 ensures that arrangements that are one swap of adjacent letters away from alphabetical are dealt with correctly.

But this logic also applies to more than just one swap. Look now at the arrangement B-C-A-D. C and A both see the same thing as for B-A-C-D, and so again will wear the same hats, but will stand in a different order. So B and D will have to wear the other hat to the one they wore for B-A-C-D. Prisoner B, who was involved in one of our swaps and saw the other, has now changed hat once, to white. Prisoner D was involved in neither swap so saw them both, has changed hat twice and is back to his original assignment of black.

It’s a fact about these arrangements that you can reach any arrangement at all by doing enough swaps of adjacent prisoners. So in fact we’ve already hit upon a complete strategy, which is as follows:

• If a prisoner sees a sub-arrangement with all the other prisoners in alphabetical order then:
• • If he is prisoner A,C,E,…, he wears white.
  • If he is prisoner B,D,F,… he wears black.

If a prisoner sees a sub-arrangement different from alphabetical order, work out how to get from alphabetical order to the new order by swapping adjacent prisoners. If it takes an even number of swaps, keep the hat assignment from rule 1. Otherwise, wear the other hat.

A change from one arrangement to another is called a permutation. In rule 2, the prisoners are working out the sign of the permutation associated with their sub-arrangement. It might not be clear that this is well-defined, that is, that you can’t get the same effect by doing two different sequences of adjacent-letter swaps, one with an odd number and one an even number. But try it for yourself and you’ll discover that you can’t.

Here’s a (relatively) easy way to determine the sign of the permutation associated with a sub-arrangement. Let’s say there are ten prisoners, and you’re prisoner J. You see the sub-arrangement H-A-D-F-C-I-B-G-E. For each of the other nine prisoners, you count up how many of the prisoners further right in the sub-arrangement (ie, with a higher number,) have a letter before them in the alphabet (ie, come before them in the ‘standard’ arrangement). So what happened in this case? Prisoner A has nobody with an earlier letter who could be standing to his right. B could only have A, but A is to his left. C however, has B standing to his right, so we count 1. Similarly, D has both C and B to his left, so we count 2. E has nobody to his left. F has B, C and E giving a count of 3. G gets a count of 1, H gives 7 and I gives 3. Now simply add up all the counts:

0+0+1+2+0+3+1+7+3=17.

An even number means it’s an even permutation and an odd number means an odd permutation. So in this case, J can see an odd sub-permutation and according to the strategy he wears a white hat. If you try adding J into the sub-permutation in any of the ten possible places, and calculate what the other prisoners would wear according to the strategy and the sub-arrangement they can see, you’ll see it works.