9.5. Petya and Vasya are playing on a $100 \times 100$ board. Initially, all cells of the board are white. On each of his turns, Petya paints one or several white cells black, which are located consecutively along a diagonal. On each of his turns, Vasya paints one or several white cells black, which are located consecutively in a vertical line. (The possible first moves of Petya and Vasya on a $4 \times 4$ board are shown in the figure on the right.) Petya makes the first move. The player who cannot make a move loses. Who wins with correct play?
Answer. Petya wins.

Solution. We will present one of the possible winning strategies for Petya. He will always make moves parallel to one of the

![](https://cdn.mathpix.com/cropped/2024_05_06_047be0e2b1db84ede7ecg-10.jpg?height=190&width=190&top_left_y=363&top_left_x=1092)
diagonals of the board (let's call it the main diagonal).

Petya's first move will be to color all the cells of the main diagonal. After this, the board is divided into two identical "staircases" (see Fig. 6). We will mentally make each staircase symmetric relative to a vertical line by shifting each horizontal row, except the first, by half a cell relative to the previous row (see Fig. 7).

![](https://cdn.mathpix.com/cropped/2024_05_06_047be0e2b1db84ede7ecg-10.jpg?height=192&width=194&top_left_y=986&top_left_x=321)

Fig. 3
![](https://cdn.mathpix.com/cropped/2024_05_06_047be0e2b1db84ede7ecg-10.jpg?height=418&width=534&top_left_y=872&top_left_x=642)

Fig. 4

As a result of the shifts, both the former verticals and the former diagonals parallel to the main diagonal have become slanted rows. At the same time, the "verticals" of one staircase are symmetric to the "diagonals" of the other. This means that for each of Vasya's moves, Petya can respond with a symmetric move in the other staircase (two such responses are shown in Fig. 7). Then, after each of Petya's moves, the situation on the "shifted" picture will remain symmetric, which means Petya will always be able to move according to the described strategy. Since the game will end (in no more than \(10^4\) moves), at some point Vasya will have no moves left, and Petya will win.

Comment. Only the correct answer and, possibly, the correct first move by Petya - 0 points.

The same, with (incorrect) attempts to set up a symmetric strategy after the first move - 1 point.