Maths Olympiad Prep

Track / Stage 7 / 106 of 300 #1506 of 1964

Problem 1506

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.2 Prove it

For positive integers t,a,b,t,a,b,a (t,a,b)(t,a,b)-[i]game[/i] is a two player game defined by the following rules. Initially, the number tt is written on a blackboard. At his first move, the 1st player replaces tt with either tat-a or tbt-b. Then, the 2nd player subtracts either aa or bb from this number, and writes the result on the blackboard, erasing the old number. After this, the first player once again erases either aa or bb from the number written on the blackboard, and so on. The player who first reaches a negative number loses the game. Prove that there exist infinitely many values of tt for which the first player has a winning strategy for all pairs (a,b)(a,b) with a+b=2005a+b=2005.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Initial Setup and Definitions:
- We are given a game with initial number t t and two positive integers a a and b b such that a+b=2005 a + b = 2005 .
- Players take turns subtracting either a a or b b from the current number on the blackboard.
- The player who first reaches a negative number loses the game.

2. Inductive Hypothesis:
- Suppose Player 1 has a winning strategy for some initial number x x where 1x2005 1 \leq x \leq 2005 .
- We need to show that Player 1 also has a winning strategy for x+2005k x + 2005k for any positive integer k k .

3. Base Case:
- Assume Player 1 wins for x x where 1x2005 1 \leq x \leq 2005 . Let P1 P_1 be the sequence of moves that ensures Player 1's win starting from x x .

4. Inductive Step:
- Consider the game starting with t=x+2005k t = x + 2005k .
- Player 1's strategy is to mimic the sequence P1 P_1 but adjusted for the larger initial number.
- Specifically, Player 1 starts by subtracting either a a or b b to reduce the number to ta t - a or tb t - b .

5. Reduction to Smaller Problem:
- After Player 1's first move, the number on the board is ta t - a or tb t - b .
- Player 2 then subtracts either a a or b b , resulting in one of the following:
t2a,tab,tba,t2b t - 2a, \quad t - a - b, \quad t - b - a, \quad t - 2b
- Notice that tab=t2005 t - a - b = t - 2005 , which is x+2005(k1) x + 2005(k-1) .

6. Inductive Argument:
- By the inductive hypothesis, if Player 1 has a winning strategy for x x , then they also have a winning strategy for x+2005(k1) x + 2005(k-1) .
- Therefore, Player 1 can continue to follow the strategy P1 P_1 adjusted for the new starting number x+2005(k1) x + 2005(k-1) .

7. Contradiction and Conclusion:
- Suppose f(t)=1 f(t) = 1 (Player 1 wins starting from t t ).
- If f(t+a)=1 f(t + a) = 1 and f(t+b)=1 f(t + b) = 1 , then f(t+a+b)=2 f(t + a + b) = 2 (Player 2 wins starting from t+a+b t + a + b ).
- This implies f(t+ab)=2 f(t + a - b) = 2 and f(t+ba)=2 f(t + b - a) = 2 , leading to a contradiction since f(ta)=1 f(t - a) = 1 and f(tb)=1 f(t - b) = 1 would imply f(t)=2 f(t) = 2 .

8. Final Proof:
- Therefore, the assumption that f(t+a+b)f(t) f(t + a + b) \neq f(t) leads to a contradiction.
- Hence, f(t+a+b)=f(t) f(t + a + b) = f(t) must hold, proving that Player 1 has a winning strategy for infinitely many values of t t .

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.