Competition problem — Number theory

Number theory Difficulty 6.5 National olympiad Prove it Austria

Alice and Bob play a game that allows the playing numbers $19$ and $20$ and the two possible starting numbers $9$ and $10$ . Alice chooses her playing number and assigns the remaining playing number to Bob while Bob independently chooses the starting number.

Alice adds her playing number to the starting number, Bob adds his playing number to the sum, then Alice again adds her playing number to this new sum and so on. The game lasts till the number $2019$ is reached or exceeded.

A player who obtains exactly $2019$ wins. If $2019$ is exceeded, the game ends in a draw.

* Show that Bob cannot win.
* Which starting number does Bob have to choose in order to prevent Alice from winning?

Solution

Let $s$ be the starting number and $a$ Alice's playing number and $b$ Bob's playing number. Furthermore, let $n$ be the number of rounds of the game (i.e., the number of times that Bob adds his number).

In order for Bob to win, the equation $s + 39n = 2019$ must have an integer solution for $n$ . But neither $s = 9$ nor $s = 10$ satisfy this condition, as neither $2010$ nor $2009$ is divisible by $39$ . Hence Bob cannot win. In fact, $51 \cdot 39 = 1989$ and $52 \cdot 39 = 2028$ .

In order for Alice to win, the equation $s + 39n + a = 2019$ has to be satisfied for some $n$ . As $28 \le s + a \le 30$ by definition, this can only work for $n = 51$ , which implies $s + a = 30$ . Therefore, we have $s = 10$ and $a = 20$ .

We conclude that Bob has to choose $9$ as starting number in order not to lose the game.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.