Квадратная таблица $n\times n$ клеток заполнена целыми числами. При этом в клетках, имеющих общую сторону, записаны числа, отличающиеся одно от другого не больше, чем на 1. Докажите, что хотя бы одно число встречается в таблице:
не менее, чем $\left[\dfrac n2\right]$ раз ($[a]$ — целая часть $a$);
не менее, чем $n$ раз.
А. А. Берзиньш
Всесоюзная математическая олимпиада школьников (1982 год, 8 класс)
Лемма. Пусть дана цепочка из $N$ клеток таблицы (каждая клетка граничит с предыдущей по общей стороне), в крайних клетках которой записаны числа $a$ и $b$ (рис. 1). Тогда 1) $|a-b|\le N-1$; 2) любое целое число $x$, заключённое между $a$ и $b$, записано в одной из клеток цепочки.
Рис. 1
Доказательство. Пусть $x_i$ — число, записанное в $i$-й клетке цепочки, тогда первое утверждение вытекает из того, что $$
|a-b|=|a-x_2+x_2-x_3+\ldots+x_{N-1}-b|\le|a-x_2|+|x_2-x_3|+\ldots+|x_{N-1}-b|,
$$
а разность двух соседних чисел не больше 1. При доказательстве второго утверждения будем для определённости считать, что $a\lt x\le b$. Двинемся по цепочке от первой клетки (с числом $a$) и найдём последнюю клетку, в которой ещё записано число, не превосходящее $x$. Эта клетка — искомая: в ней записано $x$, поскольку иначе и в следующей клетке было бы число, не превосходящее $x$ (ведь числа в соседних клетках отличаются не больше чем на 1).
а) Пусть $M$ и $m$ — наибольшее и наименьшее числа в таблице. Поскольку любые две клетки можно соединить цепочкой не более чем из $2n-1$ клеток, из неравенства леммы следует, что $|M-m|\le2n-2$. Поэтому в таблице встречается не более чем $2n-1$ различных чисел, а значит, хотя бы одно из них записано не менее чем в $\left[\dfrac{n^2}{2n-1}\right]$ клетках. Но $\dfrac{n^2}{2n-1}\gt\dfrac n2$, откуда и следует утверждение а).
б) Пусть $M_k$ и $m_k$ — наибольшее и наименьшее числа в $k$-м столбце. Если найдётся такое число $x$, что $m_k\le x\le M_k$ сразу при всех $k$ от 1 до $n$, то по второму утверждению леммы число $x$ встречается в каждом столбце, т. е. не менее $n$ раз. Если же такого числа нет, то для некоторых номеров $k$ и $l$ имеем $m_k\le M_k\lt m_l\le M_l$, т. е. любое число $k$-го столбца меньше любого числа $l$-го столбца. Применив то же утверждение к числу $y$, заключённому между $M_k$ и $m_l$, и горизонтальным цепочкам между $k$-м и $l$-м столбцами, мы получим, что число $y$ записано в каждой строке, и значит, не менее чем $n$ раз.
Заменить в задаче б) число $n$ на большее нельзя, как показывает таблица, изображённая на рисунке 2.
