Задача 88217
|
|
 |
Условие
В городе Васюки у всех семей были отдельные дома. В один прекрасный день каждая семья переехала в дом, который раньше занимала другая семья. В связи с этим было решено покрасить все дома в красный, синий или зелёный цвет, причём так, чтобы для каждой семьи цвет нового и старого домов не совпадал. Можно ли это сделать?Решение
Все семьи города можно разбить на замкнутые цепочки, в которых после каждой семьи будет стоять та, в дом которой семья переехала (может быть, будет всего одна цепочка). В цепочках из чётного числа семей, будем красить дома попеременно в синий и зелёный цвета – тогда каждая семья переедет из синего дома в зелёный или наоборот. А в тех цепочках, где число семей нечётно, покрасим один дом в красный цвет, а оставшееся чётное число домов – попеременно в синий и зелёный. Тогда все дома будут окрашены с выполнением требований задачи.
Ответ
Можно.
