Library / Estonia — Open Contests /41 of 63

Estonia — Open Contests

Combinatorics Difficulty 5.7 AIME, harder Prove it Estonia

Kati and Peeter play the following game. First, Kati writes a positive integer $a > 2016$ on the blackboard. Then Peeter starts to write more numbers on the blackboard, adding at each step the number $2016b + 1$ where $b$ is the biggest number on the blackboard. Peeter wins if at some point he writes a number divisible by $2017$ . Otherwise Kati wins. Can Kati win, and if yes, what is the smallest number $a$ she can write to win?

Solution

The number $2016b + 1$ gives the same remainder upon division by $2017$ as $-b + 1$ . Hence the remainders upon division by $2017$ are as in the sequence $b, -b+1, -(b+1)+1, \dots$ . Since $-(b+1)+1 = b$ , this sequence has period $2$ , whence there are at most $2$ different remainders. Hence the number $a$ gives the win to Kati if and only if neither $a$ nor $-a+1$ is divisible by $2017$ . Thus $a = 2017$ does not give a win, as it is divisible by $2017$ , similarly for $a = 2018$ , as $-2018+1$ is divisible by $2017$ . But for $a = 2019$ none of $2019$ or $-2019+1$ is divisible by $2017$ , giving a win.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.