Solution to March Dr. Ecco
Solution to "Grab Bag," DDJ, March 2005.
1. Yes. Player A can force a win. Here is how:
Player A: 5
Player B: 0 (forced; grabs 5) Player A: 3 (grabs 3)
Player B: 1 (forced; grabs 4)
Player A: 1 (grabs 1 and 2)
2. Player B wins when n=1 and n=3, and there is a draw when n=2 (obvious cases). A can force a draw when n=4 and n=6, although A might lose if he plays badly. When n is 5 or at least 7, the first player (player A) can always force a win by playing this series of numbers: n, n-2, n-(2+3), n-(2+3+4),..., but he should depart from this strategy once he can grab all the remaining numbers. This strategy forces B to play 0, then 1, then 2, etc., and A grabs more and more. This works for any even or odd number. Consider n=11:
Player A: 11 (first move, grabs nothing)
Player B: 0 (forced; grabs 11) (Bgrab={11})
Player A: 9 (grabs 9) (Agrab={9})
Player B: 1 (forced; grabs 10) (Bgrab={11,10})
Player A: 6 (grabs 6 and 7) (Agrab={9,6,7})
Player B: 2 (forced; grabs 8) (Bgrab={11,10,8})
Player A: 2 (grabs 2, 3, and 4)(Agrab={9,6,7,2,3,4})
Player B: 3 (forced; grabs 5) (Bgrab={11,10,8,5}) FINAL, with four numbers grabbed
Player A: 0 (grabs the rest, 1) (Agrab={9,6,7,2,3,4,1}) FINAL, with seven numbers grabbed
3. The winning situations remain the same, but the strategy changes a little. That is, B still wins for n=1 and n=3, there is a draw for n=2, A can force a draw for n=4 and n=6, and A can force a win for n=5 and for n=7 or greater.
The strategy is similar, but A will follow this series when seeding: (-n)+1, (-n)+1+2, (-n)+1+2+3, (-n)+1+2+3+4... As before, A will depart from this strategy when able to grab all the remaining numbers. This will force B to seed the series n, n-1, n-2, n-3..., playing forced as before. Note that A can block the game by seeding -n in the first turn or by following this strategy and then grabbing the lowest nongrabbed number, but then A would lose.
Example with n=5
A seeds -4 and grabs nothing.
B seeds 5 (forced) and grabs 1
A seeds -2 and grabs 3
B seeds 4 (forced) and grabs 2
A seeds 0 and grabs 5 and 4.
A wins with three grabbed numbers while B grabbed 2.
Cristian Richart and Tomas Rokicki contributed to these solutions. Cristian found the solution to question 3 and proved that in the setting of the second question, it's always possible to grab a number if there are ungrabbed ones available after the first move.
