Tag: Featured

A hundred prisoners are locked up in a prison. The warden devises the following game: he writes 100 different numbers on the foreheads of the prisoners. Then, each of the prisoners inspects the numbers on the foreheads of the others and decides to put either a black or a white hat on his head. Once the prisoners put their hats on, the warden arranges them in a line according to the numbers on their foreheads, starting with the lowest one and ascending to the highest one.

If the hats in the resulting line alternate their colors, then the prisoners will be set free. If not, the prisoners will be executed.

Can the prisoners devise a strategy that will guarantee their freedom?

Once the warden writes the numbers on the prisoners’ foreheads, they form a mental circle, arranging themselves alphabetically in it (or according to any other order they agree on). They include the warden in this mental circle and imagine he has infinity written on his forehead.

Then, each prisoner examines the sequence of 100 numbers written on the foreheads of the others, and computes the number of inversions, i.e. the pairs which are not in their natural order. The prisoners which count an even number of permutations put black hats on, and the prisoners that count an odd number of permutations put white hats on. The infinity symbol is treated as the largest number in the sequence.

For example, if a prisoner sees the sequence {2, -6, 15.5, ∞, -100, 10}, then he counts seven inversions, which are the pairs (2, -6), (2, -100), (-6, -100), (15.5, -100), (15.5, 10), (∞, -100), (∞, 10), and puts a white hat on.

Next, we prove that the devised strategy works. We consider two prisoners, P1 and P2, who are adjacent in the final line the warden forms. These two prisoners split the mental circle in two arcs: A and B.

The number of inversions P1 counts is:

I_1 = I(A)+I(B)+I(A,B)+I(A, P_1) + I(P_1, B),

where I(X) denotes the number of inversions in a sequence X, and I(X, Y) denotes the number of inversions in a pair of sequences (X, Y):

I(X) = \|x_i, x_j \in X : \quad i < j, \quad x_i > x_j\| \\
I(X, Y) = \|x \in X, y \in Y : \quad x > y\|

Similarly, the number of inversions P2 counts is:

I_2 = I(A) + I(B) + I(B, A) + I(B, P_2) + I(P_2, A)

We sum I_1 and I_2 to get:

\begin{align*}
I_1 + I_2 &= 2I(A) + 2I(B) + I(A, B) + I(B, A) \\
&+ I(A, P_1) + I(P_2, A) + I(P_1, B) + I(B, P_2) \\
&= 2(I(A) + I(B)) + \|A\|\|B\|+\|A\|+\|B\|
\end{align*}

Since \|A\| + \|B\| = 99 is an odd number, we see that I_1+I_2 is also odd. Therefore, one among P1 and P2 would have counted an even number of inversions, and one would have counted an odd number of inversions. Thus, their hats have alternating colors.