Разделы 
Дополнительно
Задача по математике - 3820
2019-06-16 
Квадратная таблица $n \times n$ клеток заполнена целыми числами. При этом в клетках, имеющих общую сторону, записаны числа, отличающиеся одно от другого не больше чем на 1. Докажите, что хотя бы одно число встречается в таблице:
а) не менее чем $[n/2]$ раз ($[а]$ - целая часть числа $а$);
б) не менее чем $n$ раз.
Решение:
б) Пусть $m_k$ и $M_k$ - наибольшее и наименьшее из чисел $k$-го столбца. Тогда в столбце встретится любое $m_k \leq x \leq M_k$. Поэтому либо существует $x$, для которого $m_k \leq x \leq M_k$ при всех $k = 1, 2, \cdots, n$, либо $M_k \geq m_k > M_p \geq m_p$ для некоторых $k$ и $p$, но тогда в каждой строке встретится любое число $у$, для которого $M_p \leq y \leq m_k$.
Квадратная таблица $n \times n$ клеток заполнена целыми числами. При этом в клетках, имеющих общую сторону, записаны числа, отличающиеся одно от другого не больше чем на 1. Докажите, что хотя бы одно число встречается в таблице:
а) не менее чем $[n/2]$ раз ($[а]$ - целая часть числа $а$);
б) не менее чем $n$ раз.
Решение:
б) Пусть $m_k$ и $M_k$ - наибольшее и наименьшее из чисел $k$-го столбца. Тогда в столбце встретится любое $m_k \leq x \leq M_k$. Поэтому либо существует $x$, для которого $m_k \leq x \leq M_k$ при всех $k = 1, 2, \cdots, n$, либо $M_k \geq m_k > M_p \geq m_p$ для некоторых $k$ и $p$, но тогда в каждой строке встретится любое число $у$, для которого $M_p \leq y \leq m_k$.
