СПбГУ 2026, 9 класс, задача 3
( баллов) На доске расставлены ладьи так, что каждая клетка доски находится под боем хотя бы одной ладьи, но каждая ладья бьет не более других ладей. Для какого наименьшего можно утверждать, что в любом клетчатом квадрате находится хотя бы одна ладья. Ладья - это шахматная фигура, которая держит под боем все клетки своей вертикали и своей горизонтали.
Ответ: .
Решение. Покажем, что для можно так расставить ладьи, что в каком-то квадрате не будет ни одной ладьи. Пронумеруем столбцы слева направо, а строки снизу вверх числами от до . В строке с номером , где расставим ладьи в столбцах с номерами , , , (в каждой такой строке будет по ладье). А в строке с номером поставим ладьи в последние столбцов. В итоге будет поставлено ладей, причем в каждом столбце будет ровно одна ладья, а в каждой строке не более ладьи. Поэтому такая расстановка ладей удовлетворяет условию задачи. Рассмотрим левый верхний квадрат . Его строки имеют номера от до . Поэтому в этих строках все ладьи стоят в столбцах с номерами не меньше, чем . Значит, они не попадают в этот квадрат.
Покажем теперь, что в квадрате обязательно располагается хотя бы одна ладья. Предположим противное. Заметим, что есть ровно строки, которые не задевают этот квадрат. В этих строках располагается не более ладьи. Поэтому есть хотя бы один столбец квадрата (пусть он имеет номер ), который не бьется этими ладьями. Аналогично есть ровно столбца, которые не задевают этот квадрат. В этих столбцах также располагается не более ладьи. Поэтому есть хотя бы одна строка квадрата (пусть она имеет номер ), которая не бьется этими ладьями. Но тогда клетка, расположенная в пересечении -й строки и -го столбца не бьется ни одной ладьей. Противоречие.