Математикадан 55-ші халықаралық олимпиада, 2014 жыл, Кейптаун

$n\ge 2$ бүтін саны берілген. Өлшемі $n\times n$ болатын ${{n}^{2}}$ бірлік шаршыдан тұратын шахмат тақтасы берілген. Егер әрбір қатарда және әрбір бағанда тек бір ғана ладья тұрса, онда $n$ ладьяның орналасуын бейбітшіл деп атаймыз. Әрбір $n$ ладьяның бейбітшіл орналасу кезінде ешқандай ${{k}^{2}}$ бірлік шаршысында ладья болмайтындай өлшемі $k\times k$ болатын тақта табылатындай ең үлкен $k$ санын табындар.

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

Ответ. Для $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$