3
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ Wikipedia explains the concept of the sign of a permutation quite well. Why don’t you go read that page (which states in the first three paragraphs the key to solving this problem) and try to understand the solution yourself. $\endgroup$ – Stella Biderman Nov 25 '17 at 15:17
  • $\begingroup$ @StellaBiderman I have obviously read the wikipedia article and also tried to understand the solution myself, otherwise I wouldn't write here. I am not so lazy! $\endgroup$ – Juan Manuel Prada Nov 25 '17 at 15:20
  • $\begingroup$ That is not at all obvious to me from your post. We regularly get lots of low quality questions that could have been easily solved by a google search, so I don’t know that you’ve put any effort into understanding the solution. Especially since no where in your post did you explain how you tried to understand the solution. Why don’t you edit the post and explain what you think the concept of the sign of a permutation is, and what aspect of it confuses you? That’ll give me a good starting point for explaining the answer. $\endgroup$ – Stella Biderman Nov 25 '17 at 15:26
  • $\begingroup$ In particular, have you ever taken a course on group theory? Do you know what a permutation is? It’s very hard to write an answer that’s understandable to you without know what you know. I don’t want to talk about $S_n$ and then find out that you don’t know what that symbol means. $\endgroup$ – Stella Biderman Nov 25 '17 at 15:32
  • $\begingroup$ @StellaBiderman I have a very clear question at the end of my post: If prisoner X doesn't know his (actual) position in the ordering, how can he calculate the sign of the permutation? Assuming he's got number "minus infinity", he (imaginary) positions himself at the end (so he is the 100th in the row) and calculates the sign of this permutation, right? As compared to the original permutation, which is 1,2,3 etc? $\endgroup$ – Juan Manuel Prada Nov 25 '17 at 15:33
0
$\begingroup$

The sign, or signature, of a permutation is a multiplicative function that maps permutations to $\{-1,1\}$. It has a number of very interesting properties, but there are two that we are interested in for this problem.

The signature function is multiplicative. If $\sigma,\tau$ are permutations then $sgn(\sigma)sgn(\tau)=sgn(\sigma\tau)$ where $\sigma\tau$ represents the permutation obtain by first applying $\tau$ and then applying $\sigma$. Although it usually matters what order permutations are applied in, in this specific context it doesn’t because $sgn(\sigma\tau)=sgn(\tau\sigma)$.

The second property that we will need is found in the first paragraph of the wikipedia article. It states that

If any total ordering of $X$ is fixed, the parity (oddness or evenness) of a permutation $\sigma$ of $X$ can be defined as the parity of the number of inversions for $\sigma$, i.e., of pairs of elements $x, y$ of $X$ such that $x<y$ but $\sigma(x)>\sigma(y)$.

From now on, we will let $\sigma$ represent the permutation that sends person $i$ to their position in the ranking. That is, person $i$ stands at position $\sigma(i)$ when the prisoners are sorted the next morning. There is one more detail to this problem that isn’t emphasized until the very end: our goal is to make it so that for any two people, $x,y$, such that $\sigma x$ and $\sigma y$ differ by one, $x$ and $y$ male opposite choices. It doesn’t matter what their choices are, merely that they need to be reversed.

Fix some prisoner, $j$, and let $\tau_j$ be the permutation that lists $j$ first, and then lists the rest of the prisoners in the order that $\sigma$ does. It is a theorem from group theory (and easily verified in this case) that, for every $\tau_j$, there exists a $\mu_j$ such that $\mu_j\tau_j=\sigma$. $\mu_j$ is the permutation that takes $j$ and moves it from its position at the front to the position it occupies in $\sigma$.

Notice that the next morning, the permutation $\tau_j$ (and therefore $sgn(\tau)$ can be calculated by prisoner $j$. However, neither $\sigma$ nor $\mu_j$ is known to the prisoner. Now, we know that $sgn(\sigma)=sgn(\tau_j)sgn(\mu_j)$ by multiplicativity. We would like it to be the case that $sgn(\tau_j)$ and $sgn(\tau_k)$ have different values whenever $\sigma(j)$ and $\sigma(k)$ differ by one. If this is the case, then we can fix a convention such as “if you get a negative signature for $\tau$ put black on the left.”

Luckily for us, this is exactly the case! Let’s call $m=sgn(\sigma)$ and note that this is the same for all prisoners. Assume that $\sigma j$ and $\sigma k$ differ by one. We have that $$sgn(\tau_j)sgn(\mu_j)=m=sgn(\tau_k)sgn(\mu_k)$$ and so $$sgn(tau_j)\neq sgn(tau_k)\iff sgn(mu_j)\neq sgn(\mu_k)$$ But $\mu_j$ just moves $j$ to their correct spot in the line-up, so $sgn(mu_j)$ and $sgn(mu_k)$ must differ when $\sigma j$ and $\sigma k$ differ by one because they’re counting exactly the same people, except one of them counts the other! If this bit isn’t obvious to you, try making a small example with 10 people and counting the number of switches by hand.

Therefore $sgn(\tau_j)$ and $sgn(\tau_k)$ always differ when $\sigma j$ and $\sigma k$ differ by one, and so it can be used to decide which gloves to wear.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.