Talk:100 prisoners: Difference between revisions
→No card viewed en route to a find needs further checking
m (→No card viewed en route to a find needs further checking: the prisoners must not interact) |
|||
| (19 intermediate revisions by 4 users not shown) | |||
Line 35:
:<b> The rules state that each prisoner may open only 50 drawers and cannot communicate with other prisoners</b><BR>
:So the start drawer is drawer_number= prisoner_number<BR>[[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 13:19, 7 November 2019 (UTC)
::That’s right, and thats why every prisoner starts exactly one full cycle length away from their card. Prisoners don’t talk to each other, but when the simulator has checked one number in the cycle it has checked them all. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 14:45, 7 November 2019 (UTC)
::Each prisoner in a particular cycle group enters that cycle at a different absolute position, but at exactly the same relative position - immediately after their target card, which itself points at (contains the 1-based index of) their start position. Every prisoner in that group needs exactly the same number of steps - the full cycle - to complete the chain and reach their target. If the cycle length is 50 or less, all prisoners with numbers in that cycle reach their card. If the cycle length is 51 or more, none of them do. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 14:55, 7 November 2019 (UTC)
:: Finally, not only does a single find (a single cyclical pathway of length <= 50) tell us that every prisoner with a number on that path can reach their card, and needs no further checking - it also tells us that once the combined (summed) lengths of the viable paths we have seen reaches 50, no more further checking of any kind at all is needed. Survival of all has been established - no room remains for any cycle-path that is long enough to fail. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 15:14, 7 November 2019 (UTC)
::: Are you trying to say, prisoner A is not in cycle I so add that cycle length and try a new one, until the right cycle is found or A is not pardoned.So you marking every drawer with number and its cycle-number and every prisoner with his number and cycle number to speed things up. [[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 16:18, 7 November 2019 (UTC)
:::: No, not quite.
:::: The '''first''' point is that the rules of the optimal strategy define '''any''' successful path from starting box to found card as a cycle. (If this is not immediately clear, consider taking '''one more''' move '''after''' we find our card. Where are we now ? Back at the start - by definition - our card contains the index of the box which the optimal strategy instructs us to start with).
:::: The '''second''' point is that when we have run the test for '''one''' prisoner, and reached their card in 50 moves or less, we have collected a full cycle of this kind, from starting box to found card, (and any next move would lead us to the start again), so now we now know the whole route/path/cycle not only for our first prisoner, but for '''every prisoner''' whose number we met on that journey from first box to found card. We now know that all of those prisoners (because their numbers are on exactly the same cyclical path) '''do''' reach their card, and reach it in exactly the same number of steps as our first prisoner.
::::The '''third''' point is that after any successful test for a single prisoner (which can also be thought of as the collection of a new cycle-path) we need to do two things: 1. Only consider prisoners whose numbers have never yet turned up on any path seen so far. 2. Exit the test for that shuffle immediately, with an '''all survive''' result, if the total count of prisoner numbers seen so far, on all successful tests, already reaches 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)
: 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)
| |||