Competition problem — Combinatorics

Library / /66 of 86

Combinatorics Difficulty 6.8 National olympiad Prove it Estonia

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?

Solution

The game lasts while the number on the blackboard stays less than $10^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 $10^9$ infinitely. When the number on the blackboard equals $10^9$ , there is no legal move. As numbers larger than $10^9$ cannot appear on the blackboard, the last move is made by the player who writes the number $10^9$ on the blackboard.

Let a number $n$ be written on the blackboard. Note that $7n + 7 \equiv n + 1 \pmod 3$ and $4n^3 + 3n + 4 \equiv n^3 + 1 \equiv n + 1 \pmod 3$ . Hence all numbers that can appear on the blackboard on the next move are congruent to $n + 1 \pmod 3$ , whence the residues repeat in cycle $1, 2, 0, 1, 2, 0, \ldots$ . As $10^9 \equiv 1 \pmod 3$ , the number $10^9$ is written by the third player $C$ .

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.