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

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

Условие

На острове все страны треугольной формы (границы прямые). Если две страны граничат, то по целой стороне. Докажите, что страны можно раскрасить в 3 цвета так, что соседние по стороне страны будут покрашены в разные цвета.

Решение

Предположим, что некоторые острова, удовлетворяющие условию задачи, невозможно покрасить в три цвета так, чтобы каждая страна была покрашена в свой цвет, а соседние страны были покрашены в разные цвета. Выберем из них остров, на котором число стран самое маленькое. Рассмотрим какую–нибудь прибрежную страну (то есть какую–нибудь страну, одной из сторон выходящую на берег). В силу выбора, весь остальной остров можно покрасить в три цвета. Но рассматриваемая страна граничит только с двумя странами, а значит, для неё запрещены только два цвета. Поэтому её тоже можно покрасить. Получили противоречие. Следовательно, карту любого острова, удовлетворяющего условию задачи, можно раскрасить в три цвета так, чтобы выполнялись требования задачи.

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

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 27
Дата 2004
задача
Номер #4

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

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