Talk:100 prisoners: Difference between revisions
→No card viewed en route to a find needs further checking
| (4 intermediate revisions by 2 users not shown) | |||
Line 51:
::::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)
: Thanks - good reference. Perhaps one to add to the task description page. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 20:00, 7 November 2019 (UTC)
Simulations need some judgement in how close one follows the actual, vs the need to ''demonstrate'' that the simulation is of the actual. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 23:32, 7 November 2019 (UTC)
: and judgement, of course, is not to be confused with naivety. The former is inevitably absent if the deeper structure of the problem remains obscure. The point of building a model is to help us understand, which often includes uncovering new efficiencies [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 02:01, 8 November 2019 (UTC)
:@Paddy3118, once you realize that all prisoners in the same cycle necessarily need the same number of attempts, the simulation amounts ''exactly'' to looking at the lengths of cycles in the cycle decomposition. There is no point pretending we don't know. And this makes the task much more interesting: I don't care too much about those 100 prisoners, but random permutations can be reused in other contexts. The amazing feat, here, is to have been able to hide cleverly the permutation stuff behind a seemingly impossible puzzle. [[User:Eoraptor|Eoraptor]] ([[User talk:Eoraptor|talk]]) 07:32, 8 November 2019 (UTC)
| |||