Kozhessnikov P.A.

In the plane, 30 points were marked, no three of which lie on the same line, and seven red lines were drawn, not passing through the marked points. Could it happen that every segment connecting any two marked points intersects at least one red line?
As is known (see, for example, problem $\underline{60323}$ ), straight lines divide the plane into a maximum of $1+{ }^{n(n+1)}$ (after drawing seven red lines, no more than 29 regions are formed. At least two points will fall into one of these regions. The segment connecting them will not intersect any line, since the regions are obviously convex.

## [ Tilings with dominoes and tiles ]  Problem 66720 Topics: [ Combinatorics (miscellaneous) ]  [Chessboards and chess pieces]

Difficulty: $3+$

Grades: $8,9,10,11$

Author: Bakayev E.V.

Petya places 500 kings on the cells of a $100 \times 50$ board so that they do not attack each other. Vasya places 500 kings on the white cells (in a chessboard coloring) of a $100 \times 100$ board so that they do not attack each other. Who has more ways to do this?

## Solution

To each of Petya's arrangements, we can assign a certain arrangement of Vasya's, and different arrangements will correspond to different ones. For each of these methods, there will be a Vasya's arrangement that cannot be obtained this way. For example, when the kings occupy all the white cells in some ten non-adjacent rows. Therefore, Vasya has more arrangements.

The first method. Let's call the right side of Petya's board the axis. Consider any arrangement by Petya. By reflecting all the kings on black cells relative to the axis, we get some arrangement by Vasya: 500 kings on white cells of a $100 \times 100$ board. Indeed, the kings on one half of the board will not attack each other because they did not attack before. And kings from different halves can attack each other only if they are adjacent to the axis of reflection. But the corresponding "black" kings have moved one cell across the axis, so they do not attack the kings from their former column.

The second method (Aliyev Rashid, 10th grade, Makhachkala). We will divide each row of Vasya's board into dominoes. The dominoes form a $100 \times 50$ board. No matter how Petya places 500 kings in the centers of the dominoes, Vasya can shift each king to the white cell of the domino. If after this some two kings attack each other, then they are in adjacent dominoes, so they attacked each other in Petya's arrangement as well.

## Answer

Vasya has more.