Difficulty: Hard

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:

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)$:

Similarly, the number of inversions P2 counts is:

We sum $I_1$ and $I_2$ to get:

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.