Track / Stage 6 / 59 of 400 #1059 of 2000

Problem 1059

National olympiad, first round

Combinatorics Difficulty 6.1 Prove it

11.2. Petya and Vasya are playing a game on an $n \times n$ checkered board. Initially, the entire board is white, except for the corner cell, which is black and contains a rook. The players take turns. Each turn, a player moves the rook horizontally or vertically, and all the cells the rook passes through (including the one it lands on) are painted black. The rook must not move through or stop on black cells. The player who cannot make a move loses; Petya moves first. Who will win with correct play?

(N. Poliansky)

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

# Answer. Petya.

Solution. One of the winning strategies for Petya is to make the longest possible vertical move on each of his turns (for example, his first move will be to go vertically to the opposite corner of the board). We will show that, acting according to this strategy, he will win.

We will call a white cell reachable if the rook can reach it from the current position in several moves along white cells. We will show that at any moment Petya will be able to move, and after each of his moves, all reachable cells will form several (no more than two) rectangles, in each of which the number of rows is greater than the number of columns, and for each of them, the rook stands in a cell adjacent to the corner cell horizontally. This is true for Petya's first move.

Fig. 6

Further, if after some of his moves this is the case, then Vasya is forced to move into one of the obtained rectangles horizontally. Let this rectangle have $r$ rows and $c$ columns, and Vasya moves $v \leqslant c$ cells. After this move, the cells of the remaining rectangle (if it was) will no longer be reachable (see Fig. 6). Since $r \geqslant c+1 \geqslant 2$ , Petya still has the option of a vertical move. After this move, the reachable cells will form rectangles $r \times (c-v)$ and $(r-1) \times (v-1)$ . In each of them, the number of rows is greater than the number of columns, because $r > c > c-v$ and $r-1 > c-1 \geqslant v-1$ . At the same time, the rook stands in a cell adjacent to the corner cell horizontally in each of these rectangles; this is what we needed to prove.

Thus, we have, in particular, proved that Petya will always be able to make a move. At the same time, the game will eventually end, because the number of white cells decreases. Therefore, he will win.

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