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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum