Задача 67438

Темы:    [ Оценка + пример ] [ Числовые таблицы и их свойства ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Глебов А.

В каждой клетке таблицы $N\times N$ записано число. Назовём клетку хорошей, если сумма чисел строки, содержащей эту клетку, не меньше, чем сумма чисел столбца, содержащего эту клетку. Найдите наименьшее возможное количество хороших клеток.

Решение

Пример (один из многих). Пусть в первой строке стоят единицы, а в остальных нули. Тогда все клетки первой строки хорошие, а остальные плохие.
Оценка.
Способ 1. Разобьём все клетки таблицы на $N$ групп по $N$ клеток так, чтобы в каждой группе все клетки находились в разных строках и разных столбцах. Пример такого разбиения для $N = 5$ см. на рисунке, для других $N$ разбиение аналогично (например, в одну группу берём главную диагональ (идущую сверху слева вниз вправо), во вторую – диагональ над ней и число в левом нижнем углу, в третью – следующую диагональ и диагональ из двух клеток слева внизу, и т.д.).

Предположим, что в какой-то группе все клетки плохие. Тогда для каждой клетки этой группы сумма чисел содержащей её строки меньше суммы чисел содержащего её столбца. Суммируя эти неравенства по всем клеткам группы, получаем, что сумма чисел во всей таблице, подсчитанная по строкам, меньше, чем эта же сумма, подсчитанная по столбцам – противоречие. Значит, в каждой группе есть хорошая клетка, и число хороших клеток не меньше числа групп, то есть не меньше $N$.
Способ 2. Допустим противное – хороших клеток может быть меньше, чем $N$. Докажем лемму:
Лемма. Если в белой таблице $N\times N$ закрасить чёрным менее $N$ клеток, то можно будет выбрать $N$ белых клеток так, чтобы все они были в разных столбцах и в разных строках.
Из леммы, назвав хорошие клетки чёрными, а остальные белыми, получим противоречие: общая сумма чисел в столбцах, отвечающих N выбранным белым клеткам, больше общей суммы чисел в строках, отвечающих этим клеткам. Но в первой сумме участвуют все $N$ столбцов, а во второй сумме все $N$ строк, откуда сумма всех чисел таблицы больше самой себя, противоречие.
Доказательство. Если чёрных клеток нет, задача очевидна. Иначе найдётся строка, в которой есть и чёрная клетка, и белая (так как чёрных меньше $N$). Вычеркнем из таблицы эту строку и столбец, проходящий через белую клетку этой строки. Осталась таблица $(N-1)\times(N-1)$, в которой чёрных клеток меньше $(N 1)$, и утверждение верно по индукции (база для доски $1\times 1$ очевидна).
Способ 3. Переставим между собой строки таблицы так, чтобы суммы чисел по строкам убывали сверху вниз, а столбцы переставим так, чтобы суммы чисел в столбцах возрастали слева направо. При этом суммы чисел в строках и столбцах не изменятся, поэтому число хороших клеток не изменится (но эти клетки могут переместиться на другие места в таблице). Тогда если какая-то клетка $К$ хорошая, то и все клетки, расположенные в таблице выше и левее неё, хорошие. Все эти клетки вместе составляют прямоугольник $\Pi(К)$, у которого правая нижняя клетка – это $К$, а левая верхняя клетка совпадает с левой верхней клеткой таблицы (обведённый прямоугольник на рисунке).

Рассуждая как в 1-м решении, заключаем, что какая-то клетка $К$ на большой диагонали таблицы, ведущей из её правого верхнего угла в левый нижний угол, является хорошей. Соответствующий прямоугольник $\Pi(К)$ состоит не менее чем из $N$ хороших клеток, причём их число равно $N$, только если $К$ – это правая верхняя или левая нижняя клетка таблицы (а прямоугольник $\Pi(К)$ состоит из всех клеток верхней строки или всех клеток левого столбца таблицы). Во всех других случаях число хороших клеток в прямоугольнике $\Pi(К)$ (а значит, и во всей таблице) превышает $N$.

Ответ

Наименьшее возможное количество хороших клеток равно $N$.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
год/номер
Номер	45
Дата	2023/24
вариант
Вариант	устный тур
задача
Номер	3