Dennis is a professor of computer science at the Courant Institute, New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at [email protected].
Last Month's Dr. Ecco Solution
Since I have a key to Dr. Ecco's apartment, I walked in one day but found it empty. Ecco had been asked by Baskerhound to solve a seemingly difficult two-person game as part of a code-breaking investigation. Ecco had taken his niece and nephew to a casino that was somehow involved. I was therefore left with this letter from Liane.
Dear Professor Scarlet,
Grab Bag is a simple game to play but difficult to win. The first player is given an empty "seed" collection Aseed and a "grab bag" Agrab. The second player is given an empty seed collection Bseed and a grab bag Bgrab. The players agree on a positive number n. Here is the general idea: The players alternate moves, where a move consists of inserting a whole number to one's own seed collection (the same number can be inserted several times). When a player does so, he or she puts into his/her grab bag any number k between 1 and n resulting from adding the just inserted number to an element of the opponent's seed collection, provided k hasn't been previously "grabbed" (that is, put into a grab bag) by either player. When all the numbers between 1 and n are grabbed, the game is over and the player with the most numbers in his/her grab bag wins.
The first move consists of inserting a number between 0 and n. Subsequently, every move consists of inserting a non-negative number less than or equal to n to the player's seed bag, and results in putting at least one ungrabbed number between 1 and n in his/her grab bag, if it is possible for the player to do so. If not possible, but there are ungrabbed numbers left, then the player may use a seed number between -n and -1 to grab a number. You can prove that it is always possible to grab a number if there are any ungrabbed ones left; the player is obligated to grab on every move.
Warm-up: Who wins when n=3?
Solution Idea:
- a. In A's first move, A cannot grab anything but must choose one of 1, 2, or 3 as a seed.
- b. B can respond by grabbing one.
- c. A can then grab at most one other number, because B has only one seed.
- d. B can then grab the last.
But life is not always so straightforward. For example, A can force a draw when n=4, but only if he/she prevents B from grabbing two numbers in B's second move.
Now here are the questions, Professor:
- Can either player force a win when n=5?
- Is there a winning strategy for either player, depending on the value of n?
- Do any of these answers change if the players could use negative seed numbers on any turn, including when it is possible to grab a number with a non-negative seed? For this scenario, we'll add a new rule: If a player blocks the game (that is, makes a move that prevents the opponent from grabbing a number when there are ungrabbed numbers left), then the blocking player loses."
DDJ
