Старые добрые ладьи.

[mikroz]

Вот эта задачка понравилась.

В клетках таблицы $n \times n$ расставлены ладьи. Известно, что, если на какой-нибудь клетке
ладьи нет, то на клетках, стоящих по вертикали и по горизонтали, которые содержат эту клетку, стоит (всего) не менее
$n$ ладей. Докажите, что общее число ладей в таблице не менее $\frac{n^2}{2}$.

[Sirion]

Назовём клетки соседними, если они находятся на одной вертикали либо на одной горизонтали.

Для начала избавимся от ладей. Поскольку всего у каждой клетки $2n-2$ соседних, перефразируя условие, получаем, что для каждой пустой клетки число соседних пустых клеток не превышает $n-2$, и требуется доказать, что всего пустых клеток не более ${n^2}/2$.
Пусть на доске $k$ пустых клеток. Для каждой пустой клетки найдём число соседних с ней, и получившиеся числа сложим. По условию, результат не должен превышать $k(n-2)$. С другой стороны, тот же результат можно получить по-другому: сначала для каждой клетки найти число её соседей по вертикали, результаты сложить, затем повторить ту же операцию для горизонталей, результаты сложить, затем сложить две получившихся суммы. При этом если, допустим, на вертикали $t$ пустых клеток, то при счёте по вертикалям каждая из них будет посчитана $t-1$ раз, и, таким образом, эта вертикаль даёт вклад в общую сумму в размере $t(t-1)$.

Нетрудно доказать, что сумма таких выражений по всем вертикалям достигает минимума, когда пустые клетки распределены по вертикалям максимально равномерно. Если забыть, что количество клеток на вертикали должно быть целым числом, мы получаем минимум $(k/n)(k/n-1)n = k(k/n-1)$. Аналогично для горизонталей. Таким образом, получаем неравенство: $2k(k/n-1) \leqslant k(n-2)$, или, после преобразований, $k \leqslant {n^2}/2$

[mikroz]

Sirion, верно