4 ms·
I'm confused... "Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look i
by dbatten 8y ago
I'm confused...
"Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers."
And, in the example given, "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners."
There's never any explanation of what happens when a prisoner opens a drawer and finds it empty. In the first example given, what happens when prisoner 5 goes in and there's nothing in drawer 5? The algorithm doesn't seem to account for this.
It seems like there's some sort of assumption that the later prisoners are gathering information from the earlier prisoners, but the problem set-up seems to preclude this? They're going into a room so they can't watch each other, the drawers are closed afterwards so they can't derive information from which drawers are open/closed, and they're not allowed to communicate.
Am I not following something?
- deleted 8y ago[deleted]
- mabbo 8y agoI think you're right that the statement doesn't make sense- or else we're both not understanding it. From what I can see, no prisoner needs any information beyond knowing their own number. Once they know that, they're just searching the cycle that their number is in to see if it's less than 50-long.
- ajanuary 8y agoThe numbers are left in the drawers once someone finds their number.
- antognini 8y agoThe statement "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners" is poorly worded. I think the author intended it to mean the information gained to you, an outside observer trying to prove this statement. There is no transfer of information from one prisoner to the next. Also, when the prisoners find their number they don't remove it. No drawers are ever empty. They just have to open a drawer that contains their number.
- falcor84 8y agoAbsolutely agreed about that sentence being poorly phrased; I've edited that now.
- dbatten 8y agoTwo things: 1) You don't take your number when you find it. I guess my brain assumed "find" meant "find and take with you to prove you found it." Perhaps a better term might be "encounter." 2) Here's a much better explanation (thanks micaeked): http://datagenetics.com/blog/december42014/index.html http://datagenetics.com/blog/december42014/index.html. Essentially, the algorithm works because following numbers to drawers will eventually create a loop (e.g., drawer 2 points to 4 points to 6 points to 2). By starting with the drawer with your number, you're guaranteed to be in a loop with your number. The only question is whether your loop is less than 50 drawers long... Furthermore, this confirms that there IS no transfer of information from previous prisoners in any way.
- chongli 8y agoThe only question is whether your loop is less than 50 drawers long... So then the question is: what proportion of the permutations of 100 numbers contain a cycle greater than 50 vertices long? Is it 30%? The claim made in the Wikipedia article is that the prisoners have around 30% chance of surviving. Edit: looks like that is the case. You can even take the limit of the number of boxes (hence prisoners) to infinity and their probability of survival never drops below 30%! This is an amazing result.
- deleted 8y ago[deleted]
- justadudeama 8y agoCan you explain to me why it is guaranteed you will be in a loop with your number?
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- laurentl 8y ago
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]