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

[avva]

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

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

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

Comments

[dimrub.livejournal.com]

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

[ymka-8.livejournal.com]

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

[oulenspiegel.livejournal.com]

Да это ж Life! :)

[master-nemo.livejournal.com]

аналогичные ассоциации, но там вроде такого исхода не ожидается?

[spamsink.livejournal.com]

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

[boffin.livejournal.com]

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

[muchacho.livejournal.com]

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

[spamsink.livejournal.com]

Нет, граф из двух вершин меняться не будет. Нужно, чтобы строго больше половины соседей было другого цвета.

[monomyth.livejournal.com]

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

[avva.livejournal.com]

любой граф

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

[komprendre.livejournal.com]

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

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

а вот и решение

[(Anonymous)]

http://arxiv.org/pdf/math/9911125

я эту статью плохо понимаю. в частности, не понимаю, как это так получается, что бесконечного графа нет. может кто-нибудь на пальцах объяснить, что там происходит?

[flaass.livejournal.com]

Бесконечный - само собой локально конечный (все степени конечны)? Иначе бессмысленно.
Для задачек 1 и 2 пример слищком прост и сразу приходит в голову, так что, может, и не стоит их разбивать на части.
А 3 - хорошая :)

[eterniel.livejournal.com]

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

[avva.livejournal.com]

Это хорошо :)

[vodianoj.livejournal.com]

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

[mi-b.livejournal.com]

искать ошибку?

[reut.livejournal.com]

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

[flaass.livejournal.com]

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

[(Anonymous)]

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

[(Anonymous)]

Очаровательно!
Почти частный случай одной леммы из моей исслы.
А занимаюсь я конкретным видом динамических систем, континуальными клеточными автоматами. Лайф, как правильно было замечено ранее :)

[avva.livejournal.com]

Ммда :-)

[http://users.livejournal.com/_navi_/]

Есть замечательная книжка Sync (http://www.amazon.com/Sync-Order-Emerges-Universe-Nature/dp/0786887214/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1218127572&sr=8-1), в ней как раз рассказывается о подобных задачах (начинается там про синхронность мерцания светлячков, а потом разговор заходит даже о работе сердечной мышцы и о социальных сетях) и связанной с ними математикой. На мой вкус правда книга написана довольно простовато, для людей без математического образования (хотя там на пальцах объясняется, что такое диффуры), но читать интересно.

Задачка хорошая, спасибо.

[sky4winder.livejournal.com]

А этой книжки нет в открытом доступе? (Яндекс не нашел)

[(Anonymous)]

ключевые слова: цепь маркова

[(Anonymous)]

Фигня какая то. ну правильно человек сказал про 2х точеный граф только если развить до квадрата, как была идея тоже здесь описана, только противоположные вершины квадрата одним цветом раскрасить, а смежные противоположным то он будет меняться раз в секунду.т.к. у него у каждой вершины 2 ее смежные другого цвета. соответсвенно каждая вершина будет менять свой цвет на противоположный.

[spamsink.livejournal.com]

Я вроде нашел удовлетворяющее меня доказательство (выросшее из глупого вопроса).

[avva.livejournal.com]

Можете прислать удаленным комментом, если хотите - я теперь знаю решение, так что мне не страшно увидеть.

[kingoleg.livejournal.com]

Игра life еще была. Только там цвета два и правила немножко другие