Unlocking Boxes: A Prisoner Puzzle Variant

I had an interesting discussion about the recent prisoner puzzle post, which reminded me of another nice problem that has a similar feel.  This problem is of the sort that can be tackled from a few different angles, from computer simulation to cocktail napkin.  I will wait until next week (or until solutions in the comments) to discuss the useful nugget of mathematics inside this one.

You are being held prisoner by the usual bloodthirsty-yet-eccentric pirates, who offer the following scenario.  In a room are 100 boxes.  For each of the boxes, which lock upon closing, there is one key which opens only that box.  The 100 keys are distributed randomly in the boxes, one key per box, and the boxes are then closed.  You may select any 50 of the boxes, which will then be broken open so that you can retrieve the keys inside, possibly allowing you to open additional boxes.  If you are able to open all of the boxes, the pirates will set you free; otherwise, you will be forced to walk the plank.

What is your probability of survival?  (As usual, generalize to breaking open k of n boxes.)

An additional variant: how does your situation change if you do not have to select all of the boxes to break open ahead of time?  That is, you are allowed to select and break open a single box, unlock any additional boxes with the resulting keys, then select and break open a second box, etc.

(Unfortunately, I do not recall where I first encountered this problem.  I think it may be from one of West’s combinatorics texts.)

This entry was posted in Uncategorized. Bookmark the permalink.

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