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

Егер $x$ және $y$ екеуі нақты оң және 20-дан кіші немесе тең болса, онда жазықтығының $(x,y)$ нүктесі $\textit{орын}$ деп болсын. \par Бастапқыда, 400 орнынан әрқайсысы бос. Аружан мен Берік осы орындарға кезек-кезекпен тастар қояды, және Аружан бірінші бастайды. Аружан өзінің әр кезекте жаңа бір қызыл тасты бос орынға салады бірақ қызыл тастардың кез келген екі орнының ара қашықтығы $\sqrt{5}$ тең емес болу қажет. Берік өзінің әр кезекте жаңа бір көк тасты бос орынға салады. (Көк тасы бар орны басқа орындардан ара қашықтығы кез келген болуы рұқсат). Егер бір ойыншының тасты қоюға мүмкіндігі жоқ болса, ойын тоқтайды. \par Берік көк тастарды қалай қойса да, Аружан $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.$