Say you have 10 players in a row. You number each player by its position in the
row: 1, 2, 3, .., 10. You then write the players' names on 10 pieces of paper,
and you randomly place the papers in 10 boxes. You place exactly one paper in
each of the boxes. The boxes are also numbered from 1 to 10.<p>You allow each player to look into half of the boxes. Each player can choose
which boxes to look into. The player "wins" if they find a paper with their
number written on it. But they can't tell anyone if they won or lost, what they
saw in the boxes, or which boxes they picked.<p>The problem then, is the following: Which boxes should each player look into,
such that the chance of all of them "winning" at the same time is as high as
possible.<p>For example, one way to put the 10 numbers in the 10 boxes is:<p>Box 1: 10<p>Box 2: 9<p>Box 3: 8<p>Box 4: 4<p>Box 5: 6<p>Box 6: 5<p>Box 7: 7<p>Box 8: 3<p>Box 9: 2<p>Box 10: 1<p>The ordering of the numbers in the boxes is a permutation of the 10 numbers.
We know that there are 10! possible ways to place the numbers in the boxes.<p>Now, consider the following strategy that player X can use to open his 5 boxes.
He first opens the box numbered X. If he sees his number in it, then he wins.
Otherwise, he saw a different number Y. He then opens the box numbered Y. If he
finds his number, he wins. Otherwise, he continues until he has opened the 5
boxes he is allowed to open.<p>If the player was allowed to open as many boxes as he likes, they he would
always win. That is because he would either find his number in a box, or
continue opening boxes he hasn't opened before. Why is this true ? Well, let's
say it isn't, and that he opens boxes 3 -> 2 -> 5 -> 7 -> 5. But that cannot
happen: The first time he opened box 5 was because he saw the number 5 in box 2.
And if he had to see box 5 again, this means that box 7 also had the number 5 in
it. In fact, the only way player X could go back to a box he has seen, is when
he finds his number (X) that will lead him back to the first box he opened.<p>Now, we know that a player "wins" if he finds his number before opening more
than 5 boxes. Or, put it differently, if the loop he follows has length at most
5. In the example above, player 2 would open box 2, which would lead him to box
9, which contains number 2, forming a loop of length 2.<p>So, when do all players "win" at the same time ? When there does not exist a
loop that has length 6 or more. Or more specifically, there is no loop of length
6, or 7, or 8, or 9, or 10.
So: P_win = 1 - P_loop(6) - P_loop(7) - P_loop(8) - P_loop(9) - P_loop(10).<p>We can show [1] that P_loop(k) = 1/k, when k > 5. We need the loop to be larger
than 5 because in this case, there can only be one such loop on the permutation.<p>But then P_win would be 1 - 1/6 - 1/7 - 1/8 - 1/9 - 1/10 or ~35.4%. In general,
if we have N players and N boxes then P_win would be:
P_win = 1 - Sum[k=n/2+1 .. n]P_loop(k)
or
P_win = 1 - ( Sum[k=1 .. N]P_loop(k) - Sum[k=1 .. N/2]P_loop(k) )
or
P_win ~= 1 - ( ln(N) - ln(N/2) ) > ~30%<p>(each sum is a harmonic series sum.)<p>[1] Why is P_loop(k) = 1/k when k > N/2 though ?<p>Let's say you have numbers 1, 2, .., k. All permutations of them are k!.
How many of those k! permutations form a loop ? Well, at the first position,
you can place any number other than '1', so you have (k-1) choices. Say you
placed number Z at position 1. Then at position Z, you can't place '1' and you
can't place 'Z', so you are left with (k-2) choices. In the last position, you
have to place number '1' to close the loop, so you have no choice. So, you have
(k-1)(k-2)(k-3)...1 ways to form a loop, or (k-1)!.<p>Therefore, with a little bit of squinting, we can see that the probability that
a random permutation has a loop on it of length exactly k is (k-1)!/k!, or 1/k.<p>We can formalize this argument as follows: There are (N choose k) ways to pick the
k places on the permutation where there exists a cycle. There are (k-1)! valid
ways to form a cycle on these k places. There are (N-k)! ways to arrange the
remaining elements on the permutation. There are N! permutations, Therefore,
P_loop(k, N) =
(N choose k)<i>(N-k)!</i>(k-1)! / N! = N! / k! / (N-k)! * (N-k)! * (k-1)! / N! = 1/k