[IMO Shortlist 2004]
Problem: A and B take turns writing a number as follows. Let N be a fixed positive integer. First A writes the number 1, and then B writes 2. Hereafter, in each move, if the current number is k, then the player whose turn it is can either write k + 1 or 2k, but no player can write a number larger than N. The player who writes N wins. For each N, determine who has a winning strategy.
Solution:
Step 1) if N is odd, A can win. This is because A can always write an odd number after which B has to write an even number and N becomes a P position
Step 2) All even numbers greater than N/2 are P-positions. This is because until N/2, we have the ability to double the number but not beyond that otherwise it will exceed N. After N/2 both players will have to increment the number by 1.
Step 3) If N = 4K or N = 4K + 2, then K is a P-position. This is because if X writes k, Y must write k+1 or 2K Then X writes 2k + 2 if Y writes k and X writes 4k if Y writes 2K. X has thus written an even number greater than N/2 and by step 2, X wins. X can be either A or B and Y is the other of the two.
Step 4) If X has a winning strategy for N = k, then X has a winning strategy for N = 4k and N = 4k + 2
Proof: Consider a game where N = 4K or 4K + 2. Based on the previous step, the goal can now be modified to write K first. How can player Y prevent X from writing K ? The answer is to jump over K. After k/2, the number can be doubled. But X can double the number again resulting in an even number that is at least equal to 2(k + 1) > N /2. So X wins by step 2.
The recursive method for defining the answer for even N is as follows:
The answer for N is the same as that for floor(N/4). To convert this recursion into an explicit answer, write N in base 4. The floor(N/4) is the same as removing the last digit when N is written in base 4. We keep removing the last digit and the resulting numbers will all be winning for the same player by the same recursion. If at some point the number obtained is odd, then A wins for this number and hence A wins for N. If the N has only 0s and 2s in its base 4 representation, then with recursion we end up with number 2. B wins in this case and therefore for N.
The moves for A involve :
Write 1 at the beginning
check if B's move has exceeded N
if N is odd, write the next odd number
if N is even and equal to 4K or 4K+2, recurse floor(N/4) as say c till you get c as odd or 0 or 2
if c is odd, then arrive at c by playing odd
if c is 0, then keep playing odd
if c is 2, then declare B winner
The moves for B similarly involve
Write 2 at the beginning
If N is odd, write the current number + 1 or current number * 2
if N is even, follow the same strategy as A
B wins only when the recursion stops at 2. Otherwise A wins with winning strategy as above.
Problem: A and B take turns writing a number as follows. Let N be a fixed positive integer. First A writes the number 1, and then B writes 2. Hereafter, in each move, if the current number is k, then the player whose turn it is can either write k + 1 or 2k, but no player can write a number larger than N. The player who writes N wins. For each N, determine who has a winning strategy.
Solution:
Step 1) if N is odd, A can win. This is because A can always write an odd number after which B has to write an even number and N becomes a P position
Step 2) All even numbers greater than N/2 are P-positions. This is because until N/2, we have the ability to double the number but not beyond that otherwise it will exceed N. After N/2 both players will have to increment the number by 1.
Step 3) If N = 4K or N = 4K + 2, then K is a P-position. This is because if X writes k, Y must write k+1 or 2K Then X writes 2k + 2 if Y writes k and X writes 4k if Y writes 2K. X has thus written an even number greater than N/2 and by step 2, X wins. X can be either A or B and Y is the other of the two.
Step 4) If X has a winning strategy for N = k, then X has a winning strategy for N = 4k and N = 4k + 2
Proof: Consider a game where N = 4K or 4K + 2. Based on the previous step, the goal can now be modified to write K first. How can player Y prevent X from writing K ? The answer is to jump over K. After k/2, the number can be doubled. But X can double the number again resulting in an even number that is at least equal to 2(k + 1) > N /2. So X wins by step 2.
The recursive method for defining the answer for even N is as follows:
The answer for N is the same as that for floor(N/4). To convert this recursion into an explicit answer, write N in base 4. The floor(N/4) is the same as removing the last digit when N is written in base 4. We keep removing the last digit and the resulting numbers will all be winning for the same player by the same recursion. If at some point the number obtained is odd, then A wins for this number and hence A wins for N. If the N has only 0s and 2s in its base 4 representation, then with recursion we end up with number 2. B wins in this case and therefore for N.
The moves for A involve :
Write 1 at the beginning
check if B's move has exceeded N
if N is odd, write the next odd number
if N is even and equal to 4K or 4K+2, recurse floor(N/4) as say c till you get c as odd or 0 or 2
if c is odd, then arrive at c by playing odd
if c is 0, then keep playing odd
if c is 2, then declare B winner
The moves for B similarly involve
Write 2 at the beginning
If N is odd, write the current number + 1 or current number * 2
if N is even, follow the same strategy as A
B wins only when the recursion stops at 2. Otherwise A wins with winning strategy as above.
No comments:
Post a Comment