I have run onto this puzzle in some other site: A hundred prisoners are gathered together by their warden. Each prisoner gets two gloves: one black and one white. They are told that they have one night in order to plan a strategy, after which no communication between them will be possible. In the morning, they are told, each prisoner will have a distinct real number painted on his forehead. Each prisoner will be able to see the numbers painted on all other prisoners, but not his own. What each prisoner needs to do is to decide which glove to put on which hand. Once all prisoners have donned all gloves, they will be placed in a long line, one beside the other, ordered according to the value of the number on their foreheads, and will be asked to hold hands. If the pairs of hands holding each other all have same-colored gloves, all 100 prisoners will be set free. Your goal is to design a strategy that will maximize the probability of this happening. I also read the solution but did not quite understand it:
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%.
Anyone can explain, I would be grateful!
My main question is: If prisoner X can't see his own number, how can he calculate the parity of the permutation of the 100 prisoners? (let alone, of course, that I don't know what the parity of a permutation is - but that's quite another story!!). Anyway, anyone who can explain in a simpler way, I would very much appreciate it!!