December 2005 Dr. Ecco's Omniheurist Corner.

December 01, 2005
URL:http://www.drdobbs.com/the-box-chip-game/184406363

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 Solution

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)ⁿ, 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

1. "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.)
2. "What if there are six chips and three guesses per color?
3. "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.

1. "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.)
2. "How well can you do if you have six chips and three guesses?"

DDJ

Solution to "Feedback Strategies," DDJ, November 2005

1. The probability of winning under FeedYes is about 0.89 when Pgood is 0.9. It cannot be better than 0.9 because if one is on the second from top row and is adjacent to the winning square, there is some chance of losing. The strategy for FeedYes consists of trying to reduce the horizontal distance to the goal to zero (or to one on rows that are an odd distance away). Calculating the probability involves the following key recurrence ideas: If you are n steps (n>0) away from the top row and 0 distance away, then your probability of hitting is the same as the probability of hitting if you are n-1 steps away and one away from column 5. Otherwise, with probability Pgood you will be one column closer to your goal and with probability 1-Pgood you will be one farther from the goal both with n-1 steps.
2. Under the FeedNo strategy, the probability is about 0.55. To compute the probability for FeedNo, assume a strategy that will take four aims to the right and three aims to the left since this gives the best likelihood of hitting the destination. Given this, there are four ways to win: All seven aims are true; three of the right aims are true and two of the left are; two of the right are true and one of the left; and one right and zero left. So, the feedback dividend is about 1.6.
3. The value of Pgood, for which the dividend ratio is highest, is not 0.75 as one might think but something around 0.772. For that value, the dividend ratio reaches 1.99. I don't believe it ever reaches 2.
4. In both the FeedNo and FeedYes cases, the analysis combines short trips: One wants to go from row 1 column 4 to row 3 column 4 in the first two moves then to row 5 column 4 in the second two moves, then row 7 column 4, and finally row 8 column 5. For FeedNo, this gives a formula like the following:

((((Pgood2)+(1-Pgood)²))³)×Pgood

1. For FeedYes, this gives a formula that is Pgood4. This gives a maximum feedback dividend of 1.75 when Pgood is 0.71.

Alan Dragoo helped with these solutions.

DDJ

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.