Track / Stage 5 / 226 of 400 #826 of 2000

Problem 826

AIME late

Combinatorics Difficulty 5.5 Find the answer

Zhendarov R.G.

From a square board of $1000 \times 1000$ cells, four rectangles of $2 \times 994$ have been removed (see figure).

On the cell marked with a star, a centaur is placed - a figure that can move one cell up, left, or diagonally right and up in a single move. Two players take turns moving the centaur. The player who cannot make a move loses. Who wins with correct play?

Your answer

Official solution

Note that the game cannot continue indefinitely: no more than 999 moves of each type can be made. Consider the lower right fragment of the board, a $3 \times 3$ square (see figure). Suppose the centaur is in cell a3. The player making a move from a3 either wins or loses.

In the first case, the second player can ensure that they make a move from this cell ( $\mathrm{a} 1 \rightarrow \mathrm{a} 2 \rightarrow \mathrm{b} 3 \rightarrow \mathrm{a} 3$ or $\mathrm{a} 1 \rightarrow \mathrm{b} 2 \rightarrow \mathrm{b} 3 \rightarrow \mathrm{a} 3$ ), and in the second case, he can force his opponent to move from a3 (a1 $\rightarrow \mathrm{a} 2 \rightarrow \mathrm{a} 3$ or $\mathrm{a} 1 \rightarrow \mathrm{b} 2 \rightarrow \mathrm{c} 3 \rightarrow \mathrm{b} 3 \rightarrow \mathrm{a} 3$ ). Therefore, with correct play, the second player wins.

## Answer

The second player.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.