Задача 110001

Темы:    [ Раскраски ] [ Геометрия на клетчатой бумаге ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]

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

Условие

Авторы: Голованов А.С., Сопкина Е.

Клетки квадрата 50×50 раскрашены в четыре цвета. Докажите, что существует клетка, с четырех сторон от которой (т.е. сверху, снизу, слева и справа) имеются клетки одного с ней цвета (не обязательно соседние с этой клеткой).

Решение

Предположим, что клетки квадрата n×n удалось раскрасить таким образом, что для любой клетки с какой-то стороны от нее нет клетки одного с ней цвета.
Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырех направлений, в котором клетки того же цвета нет. Тогда на каждую клетку каемки нашего квадрата, кроме угловых, будет указывать не более одной стрелки, а на угловую – не более двух.
Так как клеток каемки всего 4n-4 , то клеток каждого цвета не более 4n . С другой стороны, каждая из n² клеток нашего квадрата раскрашена в один из четырех цветов, т.е.

n² 4·4n.
Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при n=50 .
Несложно убедиться, что оно неверно при всех n 17 , и, следовательно, утверждение задачи верно уже в квадрате 17×17 – а заодно и в любом большем квадрате.

Уточнив немного рассуждение, можно показать, что клеток каждого цвета не более, чем 4n-4, поэтому утверждение неверно уже в квадрате 15×15 .

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1999
Этап
Вариант	4
Класс
Класс	11
задача
Номер	99.4.11.6