55-я Международная Математическая OлимпиадаЮжно-Африканская Республика, Кейптаун, 2014 год

Пусть $n\ge 2$ — целое число. Дана шахматная доска $n\times n$, состоящая из ${{n}^{2}}$ единичных клеток. Расстановка $n$ ладей в клетках этой доски называется мирной, если в каждом горизонтальном и в каждом вертикальном ряду находится ровно по одной ладье. Найдите наибольшее целое положительное $k$ такое, что для каждой мирной расстановки $n$ ладей найдется клетчатый квадрат $k\times k$, ни в одной из ${{k}^{2}}$ клеток которого нет ладьи.

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

Ответ. Для $m^2<n\le (m+1)^2$ ответ $m.$

Оценка снизу. Достаточно показать, что для $n=m^2+1:$ $k\ge m$ (вырежем такой квадрат из искомого квадрата, и добавим ладьи в него если надо).

Допустим обратное. Без ограничения общности в правом нижнем углу нет ладьи. Рассмотрим нижнюю строку, правый столбец, и оставшуюся часть разделим на $m^2$ квадратов размера $m\times m.$ В каждой отмеченной части должна быть хотя бы одна ладья, но в целом их всего $m^2+1,$ а частей $m^2+2,$ противоречие.

Оценка сверху. Достаточно показать, что для $n=m^2:$ $k\le m-1$ (вырежем искомый квадрат из такого квадрата, и добавим ладьи в него если надо).

Пронумеруем строки и столбцы от $0$ до $m^2-1$ и поставим ладьи на клетки с координатами $(ma+b,mb+a)$ для $0\leq a,b\leq m-1.$ Легко проверить, что любой квадрат $m\times m$ содержит ладью. $\quad\square$