ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110001
Темы:    [ Раскраски ]
[ Геометрия на клетчатой бумаге ]
[ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

Решение

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

n2 4·4n.

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

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .