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

Проект МЦНМО
при участии
школы 57
Задача 88217
Темы:    [ Разложение в произведение транспозиций и циклов ]
[ Раскраски ]
[ Четность и нечетность ]
Сложность: 2+
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

В городе Васюки у всех семей были отдельные дома. В один прекрасный день каждая семья переехала в дом, который раньше занимала другая семья. В связи с этим было решено покрасить все дома в красный, синий или зелёный цвет, причём так, чтобы для каждой семьи цвет нового и старого домов не совпадал. Можно ли это сделать?


Решение

Все семьи города можно разбить на замкнутые цепочки, в которых после каждой семьи будет стоять та, в дом которой семья переехала (может быть, будет всего одна цепочка). В цепочках из чётного числа семей, будем красить дома попеременно в синий и зелёный цвета – тогда каждая семья переедет из синего дома в зелёный или наоборот. А в тех цепочках, где число семей нечётно, покрасим один дом в красный цвет, а оставшееся чётное число домов – попеременно в синий и зелёный. Тогда все дома будут окрашены с выполнением требований задачи.


Ответ

Можно.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 33
Год 1970
вариант
Класс 7
Тур 1
задача
Номер 5
книга
Автор Козлова Е.Г.
Название Сказки и подсказки
задача
Номер 285

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

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