Shapovalov A.V.

On each square of a chessboard, there is a rook initially. In each move, you can remove a rook that attacks an odd number of rooks. What is the maximum number of rooks that can be removed? (Rooks attack each other if they stand on the same vertical or horizontal line and there are no other rooks between them.)
None of the rooks standing in the corner squares can be taken. Indeed, at the moment when the first of them is taken, it is attacked by exactly two rooks. Suppose it was possible to leave only the four corner rooks. Then the last rook taken was either attacked by two rooks (if it stood on the edge of the board), or by none. Contradiction. Therefore, at least five rooks will remain.

We will show how to take 59 rooks. First, we will take all the rooks from the 8th rank, except for three - a8, b8, and h8, then repeat the same with the 7th, 6th, ..., 3rd, and 1st ranks (skipping the 2nd). Now we will take the rooks from the 1st file from a3 to a7, and from the last file from h3 to h7. Next, we will take the rooks b1 and a2. Finally, we will sequentially take the rooks from b8 to b3 and from g2 to c2.

\section*{[ Degree of a vertex $\quad]$  Problem $\underline{65981}$ Topics: [pairing and grouping; bijections] $[\quad$ Algorithm theory (miscellaneous). $\quad]$}

![](https://cdn.mathpix.com/cropped/2024_05_06_d3d405875929faed9b27g-09.jpg?height=52&width=300&top_left_y=400&top_left_x=-1)  Among 49 students, each is acquainted with at least 25 others.  Prove that they can be divided into groups of two or three such that each is acquainted with everyone in their group.}

## Solution

Imagine that initially all 49 students are standing in a corridor, and we will gradually let them into the classroom. We will do this in such a way that at any moment in the classroom, the children are divided into the required groups. Let Fyodor be a student standing in the corridor. If he is acquainted with another student standing in the corridor, we will simply let them both into the classroom. Otherwise, all of Fyodor's acquaintances are already in the classroom. Since there are fewer than 50 students in the classroom, they are divided into fewer than 25 groups. Therefore, among Fyodor's acquaintances, some two are in the same group. If this is a group of two students, we will let Fyodor into the classroom, adding him to this group. If it is a group of three students, we will ask one of Fyodor's acquaintances to form a group with him, and leave the remaining students in a pair.

By gradually letting students into the classroom, we will achieve that all students are divided into the required groups.