Dr. Dobb's Journal December, 2005
"I'd be delighted," I said thinking fondly of the baby-faced huckster who had visited us a few months earlier.
Ecco began: "You have some even number n of chips, each having a different color. You put one in each box. Your adversary rearranges the boxes behind a curtain. You then rearrange them further once they're on your side of the curtain. (At the end of the game, you will be able to verify that there is a chip of each color in the boxes, so you can be sure that the adversary does no more than rearrange the boxes.) The net effect is that you can assume the rearrangement is entirely random.
"For each color, you guess 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)n, but you can do much better.
"Warm-Up: Suppose there are two chips—blue and red—and two boxes. So each guess is about just one box. Which guesses can you make so your chances of being right in both guesses is 1/2?"
"That one is easy," I said. "Guess red in the left box and blue in the right box. You'll either be both correct or both wrong."
"Right," said Ecco. "Now let's say there are four chips (n=4) whose colors are black, white, red, and green. You are allowed to guess two boxes for each chip. Number the boxes 1, 2, 3, 4. To start with, your guesses have to 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
"Now here comes the small twist. 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.
"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 2
White then try 3
Green then 4
"For convenience, we will abbreviate this as follows: black guess: 1; black -> win, red -> 2, white -> 3, green -> 4
"All initial guesses and procedures are provided before any checking occurs and the procedures may not share information. If every color is found in n/2 or fewer guesses, you win. Make sense?"
"I think I understand," I said. "We might conceptualize the situation as follows: Each color is represented by an agent who follows a procedure like the one above, possibly different procedures for different agents. 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, then leaves the scene without being able to communicate with any other agents."
"Exactly," said Ecco. "Continuing with your 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.
DDJ