Austria2019

Question

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?

Accepted Answer

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 39 = 1989 and 52 39 = 2028. In order for Alice to win, the equation s + 39n + a = 2019 has to be satisfied for some n. As 28 s + a 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.