10.15.07
Living with probability 1-ln(2)
I learned a great brainteaser while hiking in Yosemite with many a Googler this weekend. It’s from a collection called “Seven Puzzles You Think You Must Not Have Heard Correctly” (PDF), and that title is particularly apt for this one.
Here’s the question:
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
Find a strategy for them which which has probability of success exceeding 30%.
Since each prisoner has a 50/50 shot at finding his own number, you’d expect their chances of survival to be (1/2)^100, which is tiny! But that’s not quite true. Here’s the reason it’s not impossible: the number of prisoners you expect to find their own number will always be 50 no matter what your strategy. But your strategy can skew the distribution. For example, if everyone looks at the same fifty lockers, you’ll always have exactly 50 prisoners find their own numbers. The problem is to find a strategy that skews the distribution towards the extremes: either it succeeds spectacularly or fails miserably.
There’s a solution in that link above, and I’ll post my own in a few days. Give it a shot!
Nathan said,
October 16, 2007 at 7:59 am
I don’t buy it, Dan. I haven’t looked at the solution yet, because I want to give it some more thought and see if I can change my mind, but I’ll share with you my initial thoughts that make me feel like there’s no way to get 30%.
Change the objective so that instead of having to get all 100 right, you only need the first 2 to get it right. This is more likely (given that in order to get all 100 right, the first 2 also have to get theirs right). Assume wlog that person 1 picks boxes 1 – 50. Person 2 can assume person 1 got his right, since otherwise they have lost already.. The best he can do is pick the other boxes 51 -100 (since he can assume one of the 1st 50 contained the other guy’s name: not his own). But this only gives him a 50/99 chance of getting his name!
Soooo, it seems to me the best you can do even for the first 2 people both being correct is only 25.25%!
I’ll see if I can find the error of my ways, but I ain’t seeing it.
Nathan said,
October 16, 2007 at 8:30 am
Ok. I looked at the solution. I buy it. That’s a classy problem.