Estonian Math Competitions

Question

Players A, B and C are playing the following game. Initially, the number 1 is written on a blackboard. On their move, each player replaces the number n currently on the blackboard with either n+1, 7n+7, or 4n^3 + 3n + 4 at their own choice, under the condition that the new number must not be larger than 10^9. The player A makes the first move, then B takes turn, then C, after him A again etc., until some player cannot make a legal move. The player who makes the last move wins. Can any of the players win the game against every legal play by the opponents and if yes then who?

Accepted Answer

The game lasts while the number on the blackboard stays less than

1 0^{9}

, because it is possible to make a move of the first kind (replace

n

with

n + 1

). As the number on the blackboard is increased by at least

1

by every move, it cannot stay less than

1 0^{9}

infinitely. When the number on the blackboard equals

1 0^{9}

, there is no legal move. As numbers larger than

1 0^{9}

cannot appear on the blackboard, the last move is made by the player who writes the number

1 0^{9}

on the blackboard.

Let a number

n

be written on the blackboard. Note that

7 n + 7 \equiv n + 1 (mod 3)

and

4 n^{3} + 3 n + 4 \equiv n^{3} + 1 \equiv n + 1 (mod 3)

. Hence all numbers that can appear on the blackboard on the next move are congruent to

n + 1 (mod 3)

, whence the residues repeat in cycle

1, 2, 0, 1, 2, 0, \dots

. As

1 0^{9} \equiv 1 (mod 3)

, the number

1 0^{9}

is written by the third player

C

.