Question

100 prisoners problem... (famous problem)

Answer 1

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. 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. What is the prisoners' best strategy?

Answer 2

The best strategy is to open the first box at random and then open the box which has the number same as the number drawn

Answer 3

that is the given solution so far...i'm stuck on the second part of showing the property of cycle less than 50 :( .

+looking for better solution!

Answer 4

@FaiqRaees

Could you explain that?

It seems that since the numbers are put into the drawers at random then following the number to the next drawer is the same a opening another random drawer . How are your chances improved by this strategy?

(To me it would seem that each prisoner has a 50% chance of finding his number - so the chance of them ALL doing it are the same as throwing 100 heads in a row!)

I guess I have missed the key point....

Answer 5

@FaiqRaees @MrNood
To clarify what @FaiqRaees said, the solution is for the nth prisoner to look in the nth box. Then say the number in the nth box is n1. Then open box n1. Then if the number in the box n1 is n2, then open box n2 etc, until he get's his own number. This algorithm only works if all cycles of the permutation has a size less than 50. Let me think of a way to explain why this solution works...

Answer 6

@mrnood i agree to your point of choosing a random number at the start. but if each prisoner took a specific number to start with then that would improve our chance...

Answer 7

I'm gonna explain with more technical terminology because it's easier to explain... so say \(\sigma\) is your permutation function, i.e. in box n, the number in box n is \(\sigma(n)\). Then the idea of why this works is that, eventually, if you keep applying \(\sigma\), you'll eventually get n, i.e. there exists a k such that \(\sigma^k(n)=n\), where \(\sigma^k\) means the composition of \(\sigma\) k times. (For example, \(\sigma^3(n)=\sigma(\sigma(\sigma(n)))\)). This theorem is basically proved when you prove that any permutation can be written as the composition of disjoint cycles.
So how this is equivalent to the problem is this: If my prisoner is number n, then picking the nth box, he get's number \(\sigma(n)\). Then he goes to the box number \(\sigma(n)\) and the number inside the box is \(\sigma(\sigma(n))\) and so on. But by the theorem, eventually, after looking in k boxes, \(\sigma^k(n)=n\) and so he get's his number. But k (which in other words is the length of the cycle) must be smaller than 50, else the prisoner will have looked at 50 boxes without reaching the box with his number in it yet. Does that make sense?

Answer 8

Perhaps, the comment by benh will help slightly in the intuition behind why there exists a k such that \(\sigma^k(n)=n\):
http://math.stackexchange.com/questions/622616/proving-that-any-permutation-in-s-n-can-be-written-as-a-product-of-disjoint-cy/622634

Answer 9

2 questions:

1) what if a box m has number m in it? where do you go next?

2) Is this method meant to guarantte success? oor just optimise chances?
Suppose box 1 has 2 in .... box m has m+1 in it

Prisioner 1 opens box 1 then is lead to 2,3,4 etc up to 50 and never gets his number

Answer 10

1) So if I am prisoner m and pick box m which has the number m.. then I have my number!
2) I don't know if this is THE optimal solution, but this is a very good one. It does not guarantee success, it only works if all the cycles are smaller than 50 as i said: "But k (which in other words is the length of the cycle) must be smaller than 50, else the prisoner will have looked at 50 boxes without reaching the box with his number in it yet". But there is a much higher chance of survival than the prisoners randomly guessing.

Answer 11

If the prisoners randomly guess, then they each have a probability of 1/2 to get their number. So the probability that they will all get their number is \((\frac 1 2)^{100}\) which is very small. On the other hand, by this method, the probability of success is ~31% which is a huge difference! The proof of that probability is here: https://en.wikipedia.org/wiki/100_prisoners_problem#Probability_of_success

Answer 12

I'll go ahead and type up my solution before I read what everyone's said just to see how well I do.

Since it's all random and they have no way to communicate afterwards, I think they might as well just start at their own number and follow the cycle, that way their cycles are all synced up. It's all or nothing, so keeping them consistent is probably the way to go.

What if you finish a cycle before your 50 draws run out and still don't have your number? Well we need to keep them synced up, so anyone in that same cycle will have seen all the same numbers upon finishing a cycle. So you take the lowest number in the cycle, add 1 to the number until you get a number that's not in the cycle, and then continue on opening drawers from there.

Come to think of it, that strategy is probably doomed to fail, since if you and 40 other dudes just finished the same cycle and use this reasoning, your next 10 can't all be shared, so perhaps this is a bad strategy in general unless you have some certain really small cycle number.

Maybe there's some clever thing like "take the smallest number in the cycle and add it to your own number etc etc" that might end up working out better somehow, not sure, but that would probably just end up in their cycles not syncing up.

Answer 13

Or how about this entirely different strategy:

Everyone starts at their own drawer number, they take the number inside and add it to their number in mod 100 arithmetic, and then they use the remainder to choose their next box. Would this strategy be good or is this in some sense "the worst" strategy? XD