Grab Bag is a simple game to play but difficult to win.

March 01, 2005
URL:http://www.drdobbs.com/parallel/grab-bag/184406016

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:

1. a. In A's first move, A cannot grab anything but must choose one of 1, 2, or 3 as a seed.
2. b. B can respond by grabbing one.
3. c. A can then grab at most one other number, because B has only one seed.
4. 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:

1. Can either player force a win when n=5?
2. Is there a winning strategy for either player, depending on the value of n?
3. 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

Dr. Ecco Solution

Solution to "DigThat!," DDJ, February 2005.

1. 1. Six probes; see Figure. Because you know the direction of the roads as they leave an intersection, each pair on each row determines the fate of the pipe on that row and the next.
2. 2. Six hours is the best, I think. You may be able to cut out early if a detour and a return to the central path has been detected, but this is not guaranteed.

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