Задачка про гномов и их домики
Задачка про гномов и их домикиГномы, живущие в белых и красных домиках ежегодно красят свои домики, причем меняют цвет домика только те гномы, у которых более половины друзей прожили последний год в домиках другого цвета. Надо доказать, что наступит год, начиная с которого цвет некоторых домиков вообще перестанет меняться, а у остальных - будет меняться каждый год.
Гость
Ответ(ы) на вопрос:
ГостьМогу решить только в предположении, что отношение "быть другом" является отношением эквивалентности на множестве всех гномов. Тогда множество вскех гномов распадается на классы эквивалентности. Рассмотрим перекраску в одном из этих классов. 1) число гномов в этом классе четно. а) Число красных домиков равно числу белых. Для каждого гнома в красном домике в белых живет друзей на 1 больше, чем в красных, и ему придется перекрашивать. Аналогично для гномов, живущих в белых домиках. Таким образом, все домики в этом классе будут перекрашены, и это будет повторяться каждый год. б) красных домиков больше, чем белых. Жители красных домиков от труда избавлены, а все жители белых должны будут перекрасить. В итоге все домики станут одного цвета, и это уже навсегда. 2) число гномов нечетно. Сводится к 1б.
ГостьЭто задачка из дурдома? ! :)))
Не нашли ответ?
Похожие вопросы