The Box Chip Game

Sometimes a problem comes along for which a seemingly insignificant twist completely changes its character. In this puzzle, we design the odds for a new game similar to Reach for the Sky!

You have in front of you some even number n of chips each having a different color and you have also n identical, opaque latched boxes. As you watch, your adversary puts one chip in each box. He then puts all the boxes in a mixing bowl and tumbles them extensively. He then removes them and lays them out in front of you. The net effect is that you have no idea which box contains which color.

Here is what you bet on. For each color, you point to n/2 boxes where that color might be. You make all guesses about all colors before any box is opened. If you are correct about every color, you win. Otherwise you lose.

It might seem that your chances of winning are (1/2)ⁿ, but you can do better.

Warm-Up

Suppose there are two chips - blue and red - and two boxes. So you must identify the box for red and the box for blue. Which guesses can you make so your chances of being right in both guesses is 1/2?

Solution to Warm-Up

Guess red in, say, the left box and blue in the right box. You’ll either be both correct or both wrong. You might as well be consistent about the two colors. It’s no worse for you for both to be wrong than if one is wrong.

Let’s see how that generalizes. Say there are four chips (n=4) whose colors are Black, White, Red, and Green. You are to guess two boxes for each chip. Number the boxes 1, 2, 3, and 4. Your guesses will be a simple list of box numbers for each color. For example,

Black guess: 1, 2
White guess: 2, 4
Red guess: 1, 3
Green guess: 3, 4

For four chips and two guesses per color, can you figure out a way to win at least 1/6 of the time, assuming all rearrangements are equally likely? (The example just given might not achieve this.)
What if there are six chips and three guesses per color?
How does this probability generalize for n chips (n even) and n/2 guesses per color?

Now here comes the twist. It’s small, but it changes everything. Under the old rules, for each color you provide n/2 boxes as guesses. Under the new rules, for each color you provide an initial guess and a procedure for determining each next guess based on the actual color found by the previous guess.

Here is an example for Black in the case of four colors:

 Start with box 1; case result of first step is    Black, then win    Red, then try box 2    White, then try box 3    Green, then box 4

For convenience, we will abbreviate this as follows:

Black guess: 1; Black→win, Red→2, White→3, Green→4

You must provide all initial guesses and procedures before any checking occurs and the procedures may not share information. If every color is found in n/2 or fewer guesses, you win.

We might conceptualize the situation as follows: Each chip color is represented by an agent who follows a procedure like the one above, though different agents may follow different procedures. A given agent enters the room with the boxes, looks inside the boxes as dictated by his procedure, but doesn’t otherwise disturb the boxes. He or she then leaves the room without being able to communicate with any other agent, unless he loses, in which case the game is over.

Continuing with this scenario: A judge determines whether that “procedural agent” has won or not. If all agents win, then you (the person betting) win. Otherwise, the house wins. It may seem surprising, but you can do a lot better under these new rules.

How well can you do in the case of four chips and two guesses under the procedural agent assumption? (Hint: You can win over 40 percent of the time.)
How well can you do if you have six chips and three guesses?