Автор Тема: Незнайка и коротышки  (Прочитано 188 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн LtyB19i

  • Пользователь
  • Сообщений: 1
    • Просмотр профиля
Незнайка и коротышки
« : Май 04, 2018, 08:15:23 pm »
В цветочном городе каждый коротышка входит в одну их двух
политических партий. Каждое утро каждый коротышка переходит в другую
партию, если там состоит более половины его знакомых. Докажите, что
через некоторое время Незнайка либо перестанет менять свою партию,
либо будет менять ее каждый день.
Не знаю как решить помогите пожалуйста!!!
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Незнайка и коротышки
« Ответ #1 : Май 05, 2018, 11:16:11 am »
Несколько вопросов от того, кто книгу про цветочный город не читал.
Незнайка - просто один из коротышек?
Круг знакомых у каждого коротышки может изменяться, или остается постоянным? Ясно, что он не может уменьшаться  А увеличиваться?
А задачка любопытная, нестандартная...
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Незнайка и коротышки
« Ответ #2 : Май 05, 2018, 10:48:54 pm »
Задачу можно интерпретировать в терминах графов. N коротышек - вершины. Ребра - их знакомство. Все вершины покрашены в синий и красный.
На каждом ходе цвет вершины меняется, если количество соседей с противоположным цветом больше количества соседей с тем же цветом.
Нащупываются аналоги с игрой "Жизнь" Конвея. Но конечно, там ситуация несколько другая. И граф бесконечен да к тому же регулярен, и правила перекраски другие. Но что-то общее есть...
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Незнайка и коротышки
« Ответ #3 : Май 05, 2018, 10:52:59 pm »
Круг знакомых у каждого коротышки может изменяться, или остается постоянным? Ясно, что он не может уменьшаться  А увеличиваться?
Кстати, для решения задачи это не так уж важно. Граф конечен, и в конце-концов все знакомства стабилизируются. Вот это "некоторое время" и будет после "конца-концов" :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?