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