Разделы 
Дополнительно
Задача по математике - 1577
2019-01-19 
Клетки квадрата $50 \times 50$ раскрашены в четыре цвета. Докажите, что существует клетка, с четырех сторон от которой (т. е. сверху, снизу, слева и справа) имеются клетки одного с ней цвета (не обязательно соседние с этой клеткой).
Решение:
Предположим, что клетки квадрата $n \times n$ удалось раскрасить таким образом, что для любой клетки с какой-то стороны от нее нет клетки одного с ней цвета. Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырех направлений, в котором клетки того же цвета нет. Тогда на каждую клетку «каемки» нашего квадрата, кроме угловых, будет указывать не более одной стрелки, а на угловую - не более двух. Так как клеток каемки всего $4n - 4$, то клеток каждого цвета не более $4n$. С другой стороны, каждая из $n^2$ клеток нашего квадрата раскрашена в один из четырех цветов, т. е.
$n^2 \leq 4 \cdot 4n$.
Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при $n = 50$. Несложно убедиться, что оно неверно при всех $n \geq 17$, и, следовательно, утверждение задачи верно уже в квадрате $17 \times 17 $ - а заодно и в любом большем квадрате.
Замечание. Уточнив немного рассуждение, можно показать, что клеток каждого цвета не более, чем $4n - 4$, поэтому утверждение неверно уже в квадрате $15 \times 15$.
Клетки квадрата $50 \times 50$ раскрашены в четыре цвета. Докажите, что существует клетка, с четырех сторон от которой (т. е. сверху, снизу, слева и справа) имеются клетки одного с ней цвета (не обязательно соседние с этой клеткой).
Решение:
Предположим, что клетки квадрата $n \times n$ удалось раскрасить таким образом, что для любой клетки с какой-то стороны от нее нет клетки одного с ней цвета. Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырех направлений, в котором клетки того же цвета нет. Тогда на каждую клетку «каемки» нашего квадрата, кроме угловых, будет указывать не более одной стрелки, а на угловую - не более двух. Так как клеток каемки всего $4n - 4$, то клеток каждого цвета не более $4n$. С другой стороны, каждая из $n^2$ клеток нашего квадрата раскрашена в один из четырех цветов, т. е.
$n^2 \leq 4 \cdot 4n$.
Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при $n = 50$. Несложно убедиться, что оно неверно при всех $n \geq 17$, и, следовательно, утверждение задачи верно уже в квадрате $17 \times 17 $ - а заодно и в любом большем квадрате.
Замечание. Уточнив немного рассуждение, можно показать, что клеток каждого цвета не более, чем $4n - 4$, поэтому утверждение неверно уже в квадрате $15 \times 15$.
