flaass' Journal
 
 [Most Recent Entries] [Calendar View] [Friends View]

Saturday, August 9th, 2008

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

    Решение: ( Кто не хочет, может не читать )

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

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

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

    Что там на нее есть? звезды, золото, заметки... А что значит "любимая"? И сколько это - пять?
    Ну, ладно.

    Звездные дневники Ийона Тихого (Ст. Лем)
    Золотой полдень (А. Сапковский)
    Записки из подполья (Ф. Достоевский)
    Заводной апельсин (Э. Берджес)
    Змеиное молоко (М. Успенский)
    3 мушкетера (А. Дюма)

    Просите себе буквы. Обещаю ижицу не предлагать.
    8:57p
    еще раз о светофорах
    В Гугле (само собой, где же еще) нашли ссылку на статью, посвященную задачке про светофоры:
    E. Goles, J. Olivos, "Periodic behavior of generalized threshold functions" [Discrete Appl. Math. 30 (1980), 187-189]
    В статье той авторы ссылаются на более ранний, судя по всему, свой же препринт:
    "Comportement iteratif des fonctions a seuil" [Seminaire numerique #327 (IRMA, Grenoble, 1979)]

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

    UPD Ссылку исправил, по препринту из Архива:
    http://arxiv.org/pdf/math/9911125
    (нашел кто-то из читателей Аввы)
    10:39p
    для тех, кто у моря
    Венеция.

    << Previous Day 2008/08/09
    [Calendar]     		Next Day >>

ЖЖ   About LJ.Rossia.org