At the last Math Club meeting…

At the last meeting of Math Club, one of the members presented the solution to a problem he posed the week before.

There is a prison with 100 prisoners. They are all taken into a room and the warden says:

“In the room next to this one, there are 100 boxes in a row. Each of these boxes contains a slip of paper in it, and on these 100 slips of paper are your names. You may strategize as much as you’d like now, but once you have a strategy, you are each going to be sequestered in individual cells. One by one, you will be led to the room with the boxes, and you will get to open only 50 boxes in an attempt to find your name. Then you leave all room, with all the boxes exactly as you found them. You cannot change anything; you cannot take a slip from the boxes, not even your own. Then go you back to being sequestered, and the next prisoner will be led to the room. At the end, after all 100 of you have had your chance, you must tell me which box has your name in it. If all of you get your box right, then you all can leave the prison. If any of you get your box wrong, none of you can leave.

What is the best strategy for the prisoners?

The dumb “every prisoner randomly picks 50 boxes” method will give them a chance of \frac{1}{2^{100}}. You can beat that. In fact, the prisoners can come up with a strategy that will give them a pretty good chance of leaving. Not 100% (obviously), but pretty good.

And in fact, I had no idea where to even begin. But it turns out that another mathclubber came up with the right strategy. Which is awesome!

UPDATE: If you want the solution, it’s well explained on this blog post. Saves me the time of typing out the answer!

Advertisements

2 comments

  1. Nope!

    This is why when the problem was first posed, I was like: excuse me? There’s a way to do this?

    But there is! I promise to post the solution in a bit.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s