June 2000
The first player wins.
The second player will win if the target is equivalent to one of
0, 2, 4, 6 or 8 modulo 15; but 678 is equivalent to 3 modulo 15,
so the first player wins.
Put another way:
the nonnegative integers equivalent to 0, 2, 4, 6 or 8 modulo 15
will be called "winning numbers"; the other nonnegative integers
will be called "losing numbers".
You win if and only if after your turn the amount
still needed to reach the target is a "winning number".
If, at the start of your turn, the amount needed is a "losing number" (so that your opponent should lose), you can always contribute a coin which transforms it into a "winning number".
If it was 1, 3, 5, 7 or 9 modulo 15, you put in a 1-cent coin to reduce the amount needed to 0, 2, 4, 6 or 8 modulo 15
(without making the amount go negative).
If it was 10, 12 or 14 modulo 15, you put in a 10-cent coint
to reduce the amount needed to 0, 2 or 4 modulo 15.
If it was 11 or 13 modulo 15, you put in a 5-cent coin.
In all cases you will not make the amount go negative.
But if, at the start of your turn, the amount needed is a "winning
number" (so that your opponent should win and you should lose),
any coin you put in will either transform it into a "losing number"
or make the amount go negative; in either case you will lose.
If the amount started at 0, 2, 4, 6 or 8 modulo 15,
contributing a 1-cent coin will transform it to
14, 1, 3, 5 or 7 modulo 15;
contributing a 5-cent or 50-cent coin will transform it to
10, 12, 14, 1 or 3 modulo 15;
contributing a 10-cent, 25-cent or 100-cent coin will transform it to
5, 7, 9, 11 or 13 modulo 15 (or make the amount go negative).
Flippant alternate answer:
"Think outside the box." Beat the game by absconding with some of that unlimited supply of coins.
Why 15?
I guess the "15" looks mysterious without explanation.
You start by investigating, for each potential target T, whether the target T would be a "Win" for the first person or a "Loss" for the first person (and thus a win for the second person). By convention 0 is a "Loss" (since the second person just played and won). 1 is a "Win" -- the first player puts in a 1-cent coin. 2 is a Loss, 3 is a Win. T is a Win if and only if there is a coin C for which T-C is a "Loss" (because the first player can play C, and now his opponent faces T-C as the first player, and the opponent will lose). Conversely, if for EACH coin C either T-C is a Win or T-C is negative, then T is a Loss: there is no winning play.
Use those rules to build up your knowledge inductively. T=0,2,4,6,8 are all Losses, T=1,3,5,7,9,10,11,12,13,14 are Wins. Eventually you notice the periodic behavior, and once you notice it, it's easy to prove. In fact, in any such game, the outcome will EVENTUALLY be periodic, but the periodic behavior doesn't have to start right away (here it did). As to why is the period 15 in this case -- I don't know, it depends on the denominations of the coins in a way that I don't fully understand.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com