Talk:100 prisoners: Difference between revisions
m
→No card viewed en route to a find needs further checking
Line 50:
::::It goes without saying, of course, that if we find a path longer than 50 (a prisoner doesn't find their card in 50 moves), then we also exit the test for that shuffle immediately, with an '''all perish''' result. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 16:36, 7 November 2019 (UTC)
All of this can be simplified: just compute the cycle decomposition of the initial permutation. If any cycle has length >50, bad luck, otherwise they all win. This can be done in O(n) where n is the length of the permutation. <br/>See also [https://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners this]. [[User:Eoraptor|Eoraptor]] ([[User talk:Eoraptor|talk]]) 19:47, 7 November 2019 (UTC)
| |||