HMMT 二月 2010 · TEAM1 赛 · 第 2 题

英文解析

2. [ 15 ] Consider the following two-player game. Player 1 starts with a number, N . He then subtracts aproper divisor of N from N and gives the result to player 2 (a proper divisor of N is a positive divisorof N that is not equal to 1 or N ). Player 2 does the same thing with the number she gets from player 1,
   and gives the result back to player 1. The two players continue until a player is given a prime numberor 1, at which point that player loses. For which values of N does player 1 have a winning strategy?
   Answer: All even numbers except for odd powers of 2. First we show that if you are stuck with anodd number, then you are guaranteed to lose. Suppose you have an odd number ab , where a and b areodd numbers, and you choose to subtract a . You pass your opponent the number a ( b − 1). This cannotbe a power of 2 (otherwise a is a power of 2 and hence a = 1, which is not allowed), so your opponentcan find an odd proper divisor of a ( b − 1), and you will have a smaller odd number. Eventually youwill get to an odd prime and lose.
   Now consider even numbers that aren’t powers of 2. As with before, you can find an odd proper divisorof N and pass your opponent an odd number, so you are guaranteed to win.
   Finally consider powers of 2. If you have the number N = 2 , it would be unwise to choose a properkk − 1
   divisor other than 2 ; otherwise you would give your opponent an even number that isn’t a powerof 2. Therefore if k is odd, you will end up with 2 and lose. If k is even, though, your opponent willend up with 2 and you will win.
   Therefore player 1 has a winning strategy for all even numbers except for odd powers of 2.
   Team Round A