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