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

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


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

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

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