задачка (математическое)

[avva]

Третий день думаю над задачкой от flaass'а. Давно не получал такого удовольствия от задачки.

В каждой вершине графа стоит светофор, красный/зеленый. В каждую следующую секунду каждый светофор, если среди соседних с ним более половины не его цвета, меняет свой цвет (иначе остается тем же). Докажите, что через некоторое время картинка либо перестанет меняться, либо будет меняться с периодом 2 секунды.

Очень прошу, если вы знаете решение, сюда в комментарии его не писать, и подсказок никаких тоже. Вопросы/замечания/выражения восторга от того, что решили/выражения досады от того, что не решается - это пожалуйста :)

Comments

[dimrub.livejournal.com]

выражения досады от того, что не решается

[oulenspiegel.livejournal.com]

Да это ж Life! :)

[spamsink.livejournal.com]

Дополнительная задачка: чему еще можно "с горечью восхищаться", кроме простого решения задачи, которую сам решить не смог?

[boffin.livejournal.com]

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

[muchacho.livejournal.com]

"...будет меняться с периодом 2 секунды".

[monomyth.livejournal.com]

граф-то планарный, очевидно?

[avva.livejournal.com]

любой граф

еще одна задачка на тему

[komprendre.livejournal.com]

Найти такой граф такой что перед началом мало красных и много зеленых, но через какое-то количество ходов красные "побеждают".

Можно разбить задачку на уровни сложности:
1,1+) найти конкретный граф с начальным соотношением <0.5. потом с любой другой константой.
2) найти семейство графов с количеством вершин N, так что начальное количество красных светофоров является как можно меньшей функцией от N (типа корень, логарифм итп).
3) найти конкретный бесконечный граф с конечным количеством красных в начале :)

[eterniel.livejournal.com]

Если решение не знал, но решил с ходу - это куда? :)

[boffin.livejournal.com]

Они ведь меняются одновременно? Т.е.

сек 1: светофор1: К, светофор2: З
сек 2: светофор1: З, светофор2: К

и т.д.

[avva.livejournal.com]

Это хорошо :)

[avva.livejournal.com]

да

[monomyth.livejournal.com]

в том числе и disconnected? :)

[boffin.livejournal.com]

Да, Вы, конечно, правы.
Я неверно понял условие "меняться с периодом 2 секунды" вначале.

[eterniel.livejournal.com]

:))) спасибо

[avva.livejournal.com]

ага

[reut.livejournal.com]

офф: давно хотела попросить, если можно, ставить на все такие задачки какой-нибудь таг. а то иногда хочется к ним вернуться потом и очень сложно найти.
спасибо!

[vodianoj.livejournal.com]

Это раздражает. :-)

[flaass.livejournal.com]

Покамест можно вот так.

[reut.livejournal.com]

а слово "задачка" обязательно присутствует во всех?

[flaass.livejournal.com]

Не знаю. Но и этих может надолго хватить :)

[reut.livejournal.com]

проблема в том, что иногда хочется вернуться к конкретной.
а поиском у Яндекса я умею пользоваться. спасибо. :)

[ymka-8.livejournal.com]

+1, я блондинко:))) (http://ymka.bestpersons.ru/)

[flaass.livejournal.com]

Извините, если обидел :)

[muchacho.livejournal.com]

Конкретную всегда можно в мемориз.