Dennis, a professor of computer science at New York University, is the author of four puzzle books: The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (Freeman 1992, reprinted by Dover in 2004 as Dr. Ecco: Mathematical Detective); and recently Dr. Ecco's Cyberpuzzles (W.W. Norton, 2002); and Puzzling Adventures (W.W. Norton, 2005). With Philippe Bonnet, he has written Database Tuning: Principles, Experiments, and Troubleshooting Techniques (2002, Morgan Kaufmann). With Cathy Lazere, he wrote Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (1995, Copernicus/Springer). He can be contacted at [email protected].
Dr. Ecco seemed to be in a mood to muse on a cool fall day in his McDougal Street apartment. "Sometimes a problem comes along for which a seemingly insignificant twist completely changes its character," he said. "This holds particularly in games of chance. You remember our friend Jimmy Casino, don't you? Well, he invented a new game. Want to hear it?"
"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
- "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 do 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 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.
- "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?"
DDJ
