Fractal Biology

Dr. Ecco Solution

Solution to "The Box Chip Game," DDJ, December 2005.

1. Black guess: 1, 2

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


You win 4 times out of the 24 possible permutations. That's 1/6 of the time. I think that's the best one can do. See if you can do better.

2. For six chips with three guesses per color, the best I know of is 1/20. As Alan Dragoo puts it: "Guess the same half of the boxes for one half of the chips and the other half of the boxes for the other half of the chips. This gives a probability of (n/2)!×(n/2)!/n! of winning." For 6, this comes out to be 1/20.

3. Is there a nice generalization? See the Dragoo comment in the answer to 2.
4. Identify the colors with numbers:

Black -- 1
White -- 2
Red -- 3
Green -- 4


Here are the programs. The boxes are numbered 1, 2, 3, and 4 in left-to-right order.

Black: 1; Black -> win, White -> 2, Red -> 3, Green -> 4
White: 2; White -> win, Black -> 1, Red -> 3, Green -> 4
Red: 3; Red -> win, Black -> 1, White -> 2, Green -> 4
Green: 4; Green -> win, Black -> 1, White -> 2, Red -> 3


The notation means the following:

Black starts at box 1; if box 1 has a black chip, then Black wins;
if box 1 has a white chip, then Black next opens box 2;
if box 1 has a red chip, then Black next opens box 3;
and so on.


This strategy wins 10 times out of 24 permutations. To see this, consider any ordering of the colors in boxes.

1 2 3 4 win/lose
Black White Red Green win
Black White Green Red win
Black Red White Green win
Black Red Green White lose
Black Green White Red lose
Black Green Red White win
White Black Red Green win
White Black Green Red win
White Red Black Green lose
White Red Green Black lose
White Green Black Red lose
White Green Red Black lose
Red Black White Green lose
Red Black Green White lose
Red White Black Green win
Red White Green Black lose
Red Green Black White win
Red Green White Black lose
Green Black White Red lose
Green Black Red White lose
Green White Black Red lose
Green White Red Black win
Green Red Black White lose
Green Red White Black win


5. Out of the 720 possible permutations of the six elements, one can win 276 times (or more than 38 percent of the time). The agents all agree in advance on the following arbitrary association of boxes to colors (which may be completely incorrect).

Black —> box 1
White —> box 2
Red —> box 3
Green —> box 4
Blue —> box 5
Orange —> box 6


Here is the program for the agent for color X. Start at the box corresponding to color X in the arbitrary association. If you find X, then you've won, so you can stop. Otherwise, look up the color you find, say Y, in the arbitrary association and look at that box. If you find X, then you've won, so you can stop. Otherwise, look up the color you find, say Z, in the arbitrary association and look at that box. If you find X, then you've won. Otherwise, you lose.

For example, White does the following:

White: 2;
Black->1, White->win, Red->3, Green->4, Blue->5, Orange->6;
Black->1, White->win, Red->3, Green->4, Blue->5, Orange->6;


The idea for this problem comes from Peter Winkler and the solution approach for the procedural agent scenario comes from Michael Rabin. The idea is to use the color-number association (which is completely arbitrary) in a consistent manner to direct each color to the next bucket. For the algebraists: You win whenever the longest cycle in the permutation is of length n/2 or less.

DDJ