HMMT 二月 2010 · TEAM1 赛 · 第 2 题
HMMT February 2010 — TEAM1 Round — Problem 2
题目详情
- [ 15 ] Consider the following two-player game. Player 1 starts with a number, N . He then subtracts a proper divisor of N from N and gives the result to player 2 (a proper divisor of N is a positive divisor of 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 number or 1, at which point that player loses. For which values of N does player 1 have a winning strategy?
解析
- [ 15 ] Consider the following two-player game. Player 1 starts with a number, N . He then subtracts a proper divisor of N from N and gives the result to player 2 (a proper divisor of N is a positive divisor of 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 number or 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 an odd number, then you are guaranteed to lose. Suppose you have an odd number ab , where a and b are odd numbers, and you choose to subtract a . You pass your opponent the number a ( b − 1). This cannot be a power of 2 (otherwise a is a power of 2 and hence a = 1, which is not allowed), so your opponent can find an odd proper divisor of a ( b − 1), and you will have a smaller odd number. Eventually you will 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 divisor of N and pass your opponent an odd number, so you are guaranteed to win. k Finally consider powers of 2. If you have the number N = 2 , it would be unwise to choose a proper k − 1 divisor other than 2 ; otherwise you would give your opponent an even number that isn’t a power of 2. Therefore if k is odd, you will end up with 2 and lose. If k is even, though, your opponent will end 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