Game Show: Bright Lights, Big City

Another week, another Riddler. The question:

You and three of your friends are on a game show. On stage is a sealed room, and in that room are four sealed, numbered boxes. Each box contains one of your names, and each name is in one box. You and your friends take turns entering the room alone and opening up to two boxes, with the aim of finding the box containing your name. Everyone enters exactly once. Your team can confer on a strategy before stepping on stage, but there is no communication allowed during the show — no player knows the outcome of another player’s trip into the room.

Your team wins if it’s ultimately revealed that everyone found the box containing his or her name and loses if any player failed to do so. Obviously, the odds of winning are no better than 50 percent because any single player has a 50 percent chance of finding his or her own name. If each person opens two boxes at random, the chance of winning is (1/2)^4=1/16=6.25(1/2)^4=1/16=6.25 percent. Or to put it in technical terms: The chance of winning is not so great. Call this the naive strategy.

Your goal: Concoct a strategy that beats the naive strategy — one that gives the team a better chance of winning than 1/16.

Extra credit: Suppose there are 100 contestants and 100 boxes. Each player may open 50 boxes. The chance of winning by using the naive strategy is 1 in 2^100, or about 1 in 1.2×10301.2×1030. How much can you improve the team’s chances?

The way to beat this game is to look at the problem in a different light. My strategy to winning was to instead look at the chance that the first half of the players have their number in the first half of the boxes. If they are the first half of the players will find their numbers, meaning the second half are guaranteed to find theirs in the second half. The equation for this would look something like this:

\prod_{i=0}^{n/2}\left ( \frac{\frac{n}{2}-i}{n-i} \right )

Where

n =  number of players

This provides the answer of 1/6th for four players and 7.91e-15 for 50 players


		
Advertisements

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