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

Проект МЦНМО
при участии
школы 57
Задача 78787
Темы:    [ Целочисленные решетки ]
[ Доказательство от противного ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

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

Решение

Предположим противное. Поскольку соседние узлы раскрашены в разные цвета, то на горизонтальной прямой найдутся три подряд идущих узла различных цветов. Обозначим эти цвета через 1, 2 и 3, тогда над и под этими узлами должны находиться узлы 3, 4, 1 (действительно, над и под узлом 2 может быть только узел 4). Таким образом получили, что вверх и вниз чередуются узлы 1, 2, 3 с узлами 3, 4, 1, а значит, эти вертикальные прямые покрашены ровно в два цвета. Получили противоречие.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 34
Год 1971
вариант
Класс 7
Тур 2
задача
Номер 4

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

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