# Using your Head is Permitted

## September 2010 solution

Let us give each prisoner a name. For simplification, let us name them by
the integers 1..100.
Each prisoner must make a binary choice regarding which glove to put on which
hand. We want to make sure that no two adjacent prisoners make the same choice.

Let us put ourselves in the shoes of prisoner X. Prisoner X sees 99 numbers.
Let us assume, for the moment, that X himself received the number negative
infinity. The 99 visible numbers plus the one assumed, together, make up a
full list of 100 numbers, so prisoner X can, at this point, figure out the
ordering the prisoners will be in once sorted. Consider the list of names of
the prisoners, sorted by the numbers on their foreheads. This is a permutation
of the integers 1..100. Prisoner X can now calculate the sign of this
permutation. The winning strategy is for prisoner X's choice to be a function
of this permutation sign. For example, if the sign is positive he may decide
to place the black glove on his left hand, whereas if the sign were negative
he may make the opposite choice.

In reality, prisoner X's number is not negative infinity. The number he is
actually given is a real number. Let us suppose that this real number places
him in position *n* along the line. In order to get from his imagined
position (position 0) to his actual position (position *n*), he will
need to switch position with the prisoner standing next to him *n* times.
This will create the actual sorting order that the prisoners were asked to
stand in. The permutation sign for this sorting order is therefore the imagined
permutation times (-1)^{n}. In a formula:

Sgn(Π)=Sgn(Π_{n})(-1)^{n}.
Consider the prisoner to end up in position *n*+1. The corresponding
equation for him reads

Sgn(Π)=Sgn(Π_{n+1})(-1)^{n+1}.
Switching around the order of the equation we get:

Sgn(Π_{n+1})=-Sgn(Π_{n}),
which is exactly what we wanted: no two prisoners standing adjacent to each
other in the sorted line will make the same choice. The success rate for
this strategy is 100%.

Back to riddle

Back to main page