To prove that the strategy described above by Qiaochu Yuan gives the best chances of winning, the idea is as follows: consider a more fair, and more trivial variant of the game, where the rules are as before, but all open boxes remain open, so that each prisoner takes advantage of the information gathered; one may think that the boxes are simply being opened in some order by the same person. This sort of relaxation of the game is quite trivial to analyse: it consists essentially in choosing in which order to open the boxes, and of course whether or not the chosen permutation is winning, it's just random (and a priori no choice of a permutation is better than another). It turns out that the winning permutations for this game are as many as the permutations with no cycle longer that than 50. Indeed, if $\lambda(1),\dots,\lambda(100)$ is the corresponding sequence of the labels found, let's divide it in consecutive substrings so that each string ends with the lower not yet found label. This subdivision may be seen as the cycle decomposition of a permutation $\sigma$, and of course it is a lucky choice if and only if $\sigma$ has no cycle of length greater that 50. So one can't do better than that even in the original game.
|
3 | edited body | ||
|
|
||||
|
|
2 | added 126 characters in body | ||
|
To prove that the strategy described above by Qiaochu Yuan gives the best chances of winning, the idea is as follows: consider a more fair, and more trivial variant of the game, where the rules are as before, but all open boxes remain open, so that each prisoner takes advantage of the information gathered; one may think that the boxes are simply being opened in some order by the same person. This sort of relaxation of the game is quite trivial to analyse: it consists essentially in choosing in which order to open the boxes, and of course whether or not the chosen permutation is winning, it's just random (and a priori no choice of a permutation is better than another). It turns out that the winning permutations for this game are as many as the permutations with no cycle longer that 50. Indeed, if $\lambda(1),\dots,\lambda(100)$ is the corresponding sequence of the labels found, let's divide it in consecutive substrings so that each string ends with the lower not yet found label. This subdivision may be seen as the cycle decomposition of a permutation $\sigma$, and of course it is a lucky choice if and only if $\sigma$ has no cycle of length greater that 50. So one can't do better than that even in the original game. |
||||
|
|
1 |
|
||
|
To prove that the strategy described above by Qiaochu Yuan gives the best chances of winning, the idea is as follows: consider a more fair, and more trivial variant of the game, where the rules are as before, but all open boxes remain open, so that each prisoner takes advantage of the information gathered; one may think that the boxes are simply being opened in some order by the same person. This sort of relaxation of the game is quite trivial to analyse: it consists essentially in choosing in which order to open the boxes, and of course whether or not the chosen permutation is winning, it's just random. It turns out that the winning permutations for this game are as many as the permutations with no cycle longer that 50. Indeed, if $\lambda(1),\dots,\lambda(100)$ is the corresponding sequence of the labels found, let's divide it in consecutive substrings so that each string ends with the lower not yet found label. This subdivision may be seen as the cycle decomposition of a permutation $\sigma$, and of course it is a lucky choice if and only if $\sigma$ has no cycle of length greater that 50. |
||||
