- #1
Hornbein
- 2,117
- 1,742
Hardly anyone would think of this solution. I even wonder how anyone would come up with the question. And it is even more amazing that the questioner and solver were not the same person.
For a larger number of boxes (>50), the math is easy. Instead of 1 - (1/51 + 1/52 + 1/53 + ... 1/100) if would be 1 - (1/(n+1) + 1/(n+2) + 1/(n+3) + ... 1/100).Borg said:I'm curious as to how larger or smaller numbers of selected boxes would affect the outcome. Logically, if they could open more boxes, the odds generated by this strategy would increase. Likewise, selecting fewer boxes would decrease their odds. Thoughts?
It's Miltersen's 100 prisoners problem; the solution depends on whether there is a cycle of length > 50 in the arrangement of the boxes.Vanadium 50 said:Does this really take watch a 17 minute video plus ads to understand? Or can someone summarize?
You've got N slips of paper numbered 1 though N. You've got N boxes numbered 1 through N. The papers are randomly assigned to the boxes.Vanadium 50 said:Does this really take watch a 17 minute video plus ads to understand? Or can someone summarize?
This is not correct.Hornbein said:(If not there is a small chance you will luck out anyway.)
? This is just one of the cases where the prisoners all die. That happens in about 2/3s of the cases.pbuk said:This is not correct.
WLOG consider 6 prisoners with boxes containing [1:2, 2:3, 3:4, 4:1...] (i.e. a cycle of 4). Each of the prisoners 1-4 stops 1 short of the box containing their number.
Yes, that is what I quoted from your post. I demonstrated that if there is a cycle of length n > 50 then n prisoners must fail so there is no "lucking out" in this case.Hornbein said:I was however wrong in saying the prisoners might luck out in an unfavorable situation.
Assume the number of prisoners varies and they open half the boxes.Borg said:I'm curious as to how larger or smaller numbers of selected boxes would affect the outcome.
You can take Smith and Johnson. Smith's a good man, and Johnson's all right.Vanadium 50 said:You three guys - half of you come with me!
Borg said:Thoughts?
Why is the arithmetic more complicated? I assume I am missing something obvious..Scott said:For a smaller number of allowed boxes, the arithmetic isn't so simple.
Yes.hutchphd said:Why is the arithmetic more complicated? I assume I am missing something obvious.