Республиканская олимпиада по математике, 2026 год, 9 класс

Дано целое число $n\ge 4$. Какое максимальное количество клеток на доске размера $n \times n$ можно покрасить в черный цвет так, что для любых двух черных клеток $(a,b)$ и $(c,d)$ выполнено $|a-c|+|b-d|\ne n-1$? (Здесь $(x,y)$ обозначает клетку на пересечении $x$-й строки и $y$-го столбца. Клетка в левом нижнем углу доски расположена на пересечении первой строки и первого столбца). ( Абдирасулов А. )

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

Пусть $n$ это размер доски. Условие $|a-c| + |b-d| \ne n-1$ означает что нельзя брать клетки на расстоянии ровно $n-1$.

Случай 1 когда $n$ четное. Расстояние $n-1$ в этом случае нечетное. Если покрасить доску в шахматном порядке то расстояние между любыми двумя черными клетками всегда четное. Значит условие $d = n-1$ никогда не выполнится. Максимум клеток в шахматной раскраске это $n^2 / 2$.

Случай 2 когда $n$ нечетное. Расстояние $n-1$ теперь четное. Обычная шахматная раскраска не подходит. Разобьем доску на пары клеток $(x, y)$ и $(x', y')$ на расстоянии $n-1$. Из каждой такой пары можно взять максимум одну клетку.

Для нечетного $n \ge 5$ можно построить пример внутри квадрата $(n-1) \times (n-1)$ в центре доски. Если покрасить его в шахматном порядке то максимальное расстояние между черными клетками будет $n-2$. Это меньше чем $n-1$ поэтому условие выполнено.

Количество закрашенных клеток в таком квадрате $(n-1) \times (n-1)$ будет равно $(n-1)^2 / 2$. Это и есть максимальный ответ для нечетного $n$. Например для $n=5$ ответ 8 а для $n=7$ ответ 18.

Ответ: $n^2 / 2$ для четного $n$ и $(n-1)^2 / 2$ для нечетного $n$