Math Games Involving Forcing an Opponent into an Outcome

Date: 06/19/2004 at 05:22:02
From: A. K.
Subject: Tournament of Towns Question

I was looking at some of the problems from the Tournament of Towns 
2004 and came across this one:

At the beginning, the number 2004! = 1*2*3*...*2004 is written on the
blackboard.  Two players make their moves one after the other.  At
each move, the player making the move subtracts some natural number
divisible by no more than 20 different prime numbers from the number
on the board (so that the difference is non-negative), writes the
number obtained on the board, and erases the previous one.  The winner
is the player who obtains 0.  Which one of the players (the one making
the first move or the other one) has a guaranteed win, and how should
he play to get it?

I am not able to get an answer to this question.  I haven't got a
satisfactory point where I can start.  Can you help me?

Date: 06/21/2004 at 19:27:27
From: Doctor Vogler
Subject: Re: Tournament of Towns Question

Hi A.K.,

Thanks for writing to Dr Math.  That's a very interesting and very
challenging problem you ask.  It took me a while to figure it out, but
I finally did, and I was rather surprised at the answer, on two 
counts.

Not wanting to take away from you all of the fun that I got out of
your problem, I will, instead of giving you the answer with proof,
provide a few hints to help you come up with the same answer.

This type of a game is a common one that people ask mathematicians to
analyze.  The recurring feature is some kind of "state" (in your case,
the number on the chalkboard) which descends to some final state. 
Each player can choose one of several ways to change the state but
every possible move brings the state CLOSER to the final state, and
then the person whose turn it is when the final state is achieved is
either declared the winner or the loser, depending on the game.  In
particular, there must always be only finitely many states "lower" (or
closer to the final state) than any given state of the game, so that
it is impossible that the game continue forever.  (For example,
checkers and chess are not games of this style, because you could
continue them indefinitely with inane moves, although some of the same
principles here could be applied to those games.)

So I always analyze these kinds of games from the end back.  The goal
is to decide which states are "losing" states, and which states are
"winning" states.  A winning state is one from which there is some
possible move that will either win the game immediately or give your
opponent a losing state.  A losing state is just the opposite, a state
from which EVERY possible move will either lose the game immediately
or give your opponent a winning state.

So we start with the final state of the game and work backward.  For
example, if the winner is the one who achieves the final state (as in
your game), then all of the states from which you can win in one move
are winning states.  Then we look at the smallest or lowest states
(nearest to the final state) not in that category, and generally every
possible move will give your opponent a winning state, so these are
losing states.  Then we step back again and ask which are all of the
states from which you can give your opponent one of those losing 
states.  And so on and so forth.

Generally (but not always) we can find a pattern and we can make a
statement like, "All states with the following attribute are winning
states, and all other states are losing states."  Once you've found
the pattern, all you need to do is prove that every winning state has
some move that will either win the game immediately or give the
opponent a losing state (according to your attribute), and that every
losing state has the unfortunate feature that every move will either
lose the game immediately or give the opponent a winning state.

You might notice that the requirement for a losing state is much more
strict than for a winning state, since EVERY move has to give your
opponent a winning state.  That is true, and it means that for most
games there are many more winning states than there are losing states.
In particular, the first player usually has a winning strategy,
unless the initial state was carefully chosen to be a losing one.

With all that said, you can now analyze your game just like the rest
of us....

Except for one problem:  The smallest losing state is a number that's
already bigger than your calculator can display, and now how do you
check all the next states to find the next-smallest losing state?  And
you should give it some thought and decide what that smallest losing
state is.  I did, and it wasn't hard, and it turned out to be more
important than I had at first realized.  And now you should apply the
same principle that told you to start with the closest thing to the
final state:  Simplify, simplify, simplify!

Change that number 20 to 1.  Now you have to subtract a number which
is a power of a prime.  What is the smallest losing state?  What are
the first five or ten losing states?  Speculate about what all losing
states might be.  Can you prove it?  That is, can you prove that every
winning state has some move you can make to give the opponent a losing
state, and every move from a losing state will give the opponent a
winning state?  Now change the 20 to 2, and ask the same questions. 
If necessary, try 3 and others as well.  Notice a pattern and 
speculate about what the set of losing positions would look like for
the game using 20 primes.  Can you prove it?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions, because I was eventually able to solve the
problem and prove it.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/