Top.Mail.Ru
? ?
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (математическое) [авг. 7, 2008|04:27 pm]
Anatoly Vorobey
Третий день думаю над задачкой от flaass'а. Давно не получал такого удовольствия от задачки.

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

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

Comments:
[User Picture]From: dimrub
2008-08-07 03:18 pm

выражения досады от того, что не решается
(Ответить) (Thread)
[User Picture]From: ymka_8
2008-08-07 04:07 pm
+1, я блондинко:)))
(Ответить) (Parent) (Thread)
[User Picture]From: oulenspiegel
2008-08-07 03:18 pm
Да это ж Life! :)
(Ответить) (Thread)
[User Picture]From: master_nemo
2008-08-07 06:04 pm
аналогичные ассоциации, но там вроде такого исхода не ожидается?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: spamsink
2008-08-07 03:23 pm
Дополнительная задачка: чему еще можно "с горечью восхищаться", кроме простого решения задачи, которую сам решить не смог?
(Ответить) (Thread)
[User Picture]From: boffin
2008-08-07 03:42 pm
Кажется я неправильно понял условие задачи.
Ведь если есть граф из двух вершин в которых изначально цвета у светофоров разные, то каждую секунду каждый из светофоров будет менять свой цвет (т.к. среди соседних, а у него один единственный сосед, более половины не его цвета).
И это будет продолжаться бесконечно. Разве нет?
(Ответить) (Thread)
[User Picture]From: muchacho
2008-08-07 03:43 pm
"...будет меняться с периодом 2 секунды".
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: monomyth
2008-08-07 03:44 pm
граф-то планарный, очевидно?
(Ответить) (Thread)
[User Picture]From: avva
2008-08-07 03:45 pm
любой граф
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
From: komprendre
2008-08-07 03:47 pm

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


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

Можно разбить задачку на уровни сложности:
1,1+) найти конкретный граф с начальным соотношением <0.5. потом с любой другой константой.
2) найти семейство графов с количеством вершин N, так что начальное количество красных светофоров является как можно меньшей функцией от N (типа корень, логарифм итп).
3) найти конкретный бесконечный граф с конечным количеством красных в начале :)
(Ответить) (Thread)
From: (Anonymous)
2008-08-07 09:16 pm

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

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

я эту статью плохо понимаю. в частности, не понимаю, как это так получается, что бесконечного графа нет. может кто-нибудь на пальцах объяснить, что там происходит?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: eterniel
2008-08-07 03:47 pm
Если решение не знал, но решил с ходу - это куда? :)
(Ответить) (Thread)
[User Picture]From: avva
2008-08-07 03:48 pm
Это хорошо :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: reut
2008-08-07 03:56 pm
офф: давно хотела попросить, если можно, ставить на все такие задачки какой-нибудь таг. а то иногда хочется к ним вернуться потом и очень сложно найти.
спасибо!
(Ответить) (Thread)
[User Picture]From: flaass
2008-08-07 04:02 pm
Покамест можно вот так.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2008-08-07 04:28 pm
Интересно, что для бесконечных графов (локально конечных, разумеется) это утверждение, вообще говоря, уже неверно. Например, на бесконечном двоичном дереве можно легко получить любой период.
(Ответить) (Thread)
From: (Anonymous)
2008-08-07 04:45 pm
Очаровательно!
Почти частный случай одной леммы из моей исслы.
А занимаюсь я конкретным видом динамических систем, континуальными клеточными автоматами. Лайф, как правильно было замечено ранее :)
(Ответить) (Thread)
[User Picture]From: avva
2008-08-07 04:49 pm
Ммда :-)
(Ответить) (Parent) (Thread)
[User Picture]From: _navi_
2008-08-07 04:52 pm
Есть замечательная книжка Sync, в ней как раз рассказывается о подобных задачах (начинается там про синхронность мерцания светлячков, а потом разговор заходит даже о работе сердечной мышцы и о социальных сетях) и связанной с ними математикой. На мой вкус правда книга написана довольно простовато, для людей без математического образования (хотя там на пальцах объясняется, что такое диффуры), но читать интересно.

Задачка хорошая, спасибо.
(Ответить) (Thread)
[User Picture]From: sky4winder
2008-08-07 10:08 pm
А этой книжки нет в открытом доступе? (Яндекс не нашел)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2008-08-07 05:26 pm
ключевые слова: цепь маркова
(Ответить) (Thread)
From: (Anonymous)
2008-08-07 10:04 pm
Фигня какая то. ну правильно человек сказал про 2х точеный граф только если развить до квадрата, как была идея тоже здесь описана, только противоположные вершины квадрата одним цветом раскрасить, а смежные противоположным то он будет меняться раз в секунду.т.к. у него у каждой вершины 2 ее смежные другого цвета. соответсвенно каждая вершина будет менять свой цвет на противоположный.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: spamsink
2008-08-07 10:45 pm
Я вроде нашел удовлетворяющее меня доказательство (выросшее из глупого вопроса).
(Ответить) (Thread)
[User Picture]From: avva
2008-08-08 09:20 am
Можете прислать удаленным комментом, если хотите - я теперь знаю решение, так что мне не страшно увидеть.
(Ответить) (Parent) (Thread) (Развернуть)