9.2. Vasya has thought of 8 cells on a chessboard, none of which lie in the same row or column. On his turn, Petya places 8 rooks on the board, none of which attack each other, and then Vasya indicates all the rooks standing on the thought-of cells. If the number of rooks indicated by Vasya on this turn is even (i.e., 0, 2, 4, 6, or 8), then Petya wins; otherwise, all the pieces are removed from the board and Petya makes the next move. In the least number of moves, how many moves will Petya need to guarantee a win?

(I. Bogdanov)
Answer. In 2 moves.

Solution. First, we will show how Pete can win in 2 moves. On his first move, he will place 8 rooks along the diagonal of the board. If he hasn't won yet, there is an odd number of cells on the diagonal that Vasya has thought of. In particular, there is both a cell $A$ that Vasya has thought of and a cell $B$ that he hasn't.

On his second move, let Pete place rooks on 6 diagonal cells, excluding $A$ and $B$, as well as on cells $C$ and $D$, which lie in the same rows as $A$ and $B$ respectively, and in the same columns as $B$ and $A$ respectively. Each new rook is either in the same row or in the same column as $A$, so

![](https://cdn.mathpix.com/cropped/2024_05_06_d14785678fb6016bc2aeg-1.jpg?height=295&width=302&top_left_y=270&top_left_x=2444)

Fig. 1 Vasya could not have thought of their cells. 

This means that in the new configuration of rooks, the number of cells thought of by Vasya has decreased by exactly one, making it even, and Pete wins.

It remains to show that Pete cannot guarantee a win in one move. Suppose he managed to do so. By rearranging the columns of the board, we can assume that he made his first move as shown in Fig. 1; then he will not win if Vasya's cells are the gray-marked ones in the same figure.

Comment. Only the correct answer - 0 points.

Proving only that Pete cannot win in one move - 1 point.

Proving only that Pete can guarantee a win in two moves - 6 points.

Providing a correct algorithm that allows Pete to guarantee a win in 2 moves (possibly without justification and without proving the impossibility of a guaranteed win in 1 move) - no less than 4 points.