Чертей рисую (flaass) wrote,
Чертей рисую
flaass

This journal has been placed in memorial status. New entries cannot be posted to it.

Category:

решение задачки

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

Решение:
Во-первых, если б светофоры меняли цвет не разом, а по очереди, то задача была бы тривиальна, и картинка бы непременно стабилизировалась: ибо при каждом изменении количество "разноцветных" ребер строго уменьшается.
Но здесь так оно не работает, да и не должно: ведь появляются откуда-то циклы длины 2!
А мы заменим граф. Возьмем две копии множества вершин, и соединим вершины из разных копий, если их прообразы соединены. Чтоб совсем гладко, соединим меж собой две копии одной и той же вершины, если ее степень четна.
А теперь будем менять по очереди: сначала по цветам одной доли вычисляем цвета в другой доле, потом по полученным цветам вычисляем новые цвета первой доли и т.д.
Что картинка стабилизируется, теперь очевидно, как и выше. И совсем легко понять, что больше делать ничего не надо: задача решена :)


Нашли трое: jedal на пару с urkudом, и безымянный сотрудник конторы Гугл по имени Томаш Чайка.

Еще возникла попутная задачка:

komprendre: Найти такой граф такой что перед началом мало красных и много зеленых, но через какое-то количество ходов красные "побеждают".
Уточняю: надо выбрать какое-то N и придумать бесконечную серию конечных графов, в каждом из которых вначале не более N красных вершин, а в конце все красные.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 21 comments