Dr. Ecco Solution

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

  1. Black guess: 1, 2
    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:
    5. 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).
    6. 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

Back to Article