Solution
I received solutions from Mark Rickert, Joseph DeVincentis, Larry Carter, Erich Friedman, Alberto Monteiro, Stephen Morris, Jim Tilley, John Guilford, and John Sullivan. There were also several incorrect solutions. So while the problem is not difficult, it is quite easy to be led astray.
Here is the solution derived from notes of John Sullivan and Jim Guilford.
Sullivan suggests a bin interpretation: one bin for each prime p that divides N, with the capacity of the bin equal to the exponent of p. Players place stones in the bins; any overflow results in a draw.
One bin: Alice wins if capacity is odd; Bob wins otherwise. This is the case N = pk.
Two bins with capacities that differ by at most 1: Bob wins if the capacities are equal; he places a stone in the bin that Alice did not use on her move. Alice wins if they differ by one; she places a stone in the larger bin, and thereafter follows the strategy of Bob just given. This is the case N = pk qk or pk qk + 1.
Two bins, not as above: suppose one player has a winning strategy. Then the other player places stones only into the smaller bin. It will overflow before the first player can win.
Three or more bins: A draw can always be forced. If either player faces a losing move, at least one of bins would be full and the player can cause it to overflow.
[Back to Problem 1235]
© Copyright 2017 Stan Wagon. Reproduced with permission.