59-я Международная Математическая Oлимпиада Румыния, Клуж-Напока, 2018 год

На координатной плоскости отмечены точки $(x, y)$ с целыми положительными координатами $x$ и $y$, не превосходящими 20.
Вначале все 400 отмеченных точек не заняты. Аня и Ваня делают ходы по очереди, Аня ходит первой. Своим ходом Аня кладёт в ещё не занятую отмеченную точку новый красный камень, причём расстояние между любыми двумя точками с красными камнями не должно равняться $\sqrt5.$ Ваня своим ходом кладёт в ещё не занятую отмеченную точку новый синий камень. (Точка с синим камнем может находиться на произвольном расстоянии от других занятых точек.) Игра останавливается, когда кто-то из игроков не может сделать ход.
Найдите наибольшее $K$, при котором Аня сможет разместить не менее чем $K$ красных камней независимо от действий Вани.

Комментарий/решение

Ответ: $K=100.$

Ясно, что условие равносильно с тем, что у нас есть доска $20\times 20$ и красные камни не должны стоять на клетках "хода коня".

Стратегия Анны: Сделаем шахматную раскраску. Анна на каждом своем шагу будет ставить красный камень только на черные клетки. Никакие две черные клетки не связанны ходом коня, поэтому запрещенное расположение сохраняется.

В общем черных клеток $20\cdot 20\div 2=200,$ причем Анна точно успеет занять хотя бы половину из них, то есть $K\ge 200\div 2=100.$

Стратегия Ивана: Разделим искомую таблицу на куски $4\times 4.$ Сделаем следующую раскраску

$$\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2\\ 2 & 1 & 4 & 3\\ 4 & 3 & 2 & 1 \end{pmatrix}$$

Мы получаем разбиение данной доски на $4$ цикла ходов коня.

Если Анна поставит красный камень на цикл с номером $i,$ то Иван поставит синий камень в противоположную клетку в цикле $i.$ Тогда в каждом цикле будет максимум один красный камень, то есть в каждом куске будет максимум $4.$

Кусков в общем $25,$ тогда $K\le 4\cdot 25=100.$