Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет flaass ([info]flaass)
@ 2008-08-05 18:07:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
олимпиада еще не началась
Настал момент написать что-нибудь об олимпиаде. Начнем с подготовки.

Всех привезли под Тверь, в санаторий на берегу Волги, и оставили на три недели.
6 человек команды, еще где-то 30 подрастающей смены и несколько "тренеров".
Очень плотно пахали: сначала двухдневная вступительная олимпиада, по которой смену поделили на три группы по уровню.
Потом - каждый день занятия. С утра три часа, и после обеда три часа. Мы рассказываем, даем задачи, они решают, рассказывают, мы замечаем ошибки и отсылаем думать дальше. Или, если все пошло слишком хорошо и все заранее заготовленные задачи уже решены, а до обеда время еще есть, срочно соображаем, чего бы добавить.
В свободное время мы (тренеры) делаем шашлык, иногда купаемся в Волге, но чаще сочиняем будущие занятия и подбираем задачки на будущие олимпиады и матбой. Или делимся друг с другом, кто что рассказал, кто что собирается, у кого кто как решал, и вообще чего есть в математике интересного.
(Для последнего я завел специальный блокнотик: записей там набралось несколько абзацев, но над каждым хорошо бы подумать долго и основательно.)

Да, и по вечерам красное вино под общий треп :)

Задачка 30летней давности. Я ее узнал на собственных сборах, в 77м. Никто ее тогда не решил, а потом все с горечью восхищались, какое решение простое.
И на этих никто не решил.
Если кто знает решение, не рассказывайте плиз. А если кто сам решит - обязательно рассказывайте: вы будете первым известным мне человеком, кто ее решил!

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


(Читать комментарии) - (Добавить комментарий)


[info]jedal@lj
2008-08-08 09:54 (ссылка)
Рассмотрим множество всех возможных состояний, с метрикой \sum s_i s'_j (сумма по парам соседних вершин i и j исходного графа; s_i / s'_i -- \pm1 в зависимости от цвета i-й вершины в первом/втором состоянии). Каждую секунду мы идем из состояния в ближайшее. Значит, рано или поздно застрянем на паре ближайших.

(Сначал думал сам, потом вместе с [info]urkud@lj.)

(Ответить) (Ветвь дискуссии)


[info]flaass@lj
2008-08-08 10:17 (ссылка)
Уточните, что значит "ближайшая". Ибо я привык к метрикам неотрицательным :)

(Ответить) (Уровень выше) (Ветвь дискуссии)

Errata
[info]jedal@lj
2008-08-08 10:39 (ссылка)
Там должно быть не ближайшее, а дальнейшее :-) — из состояния x в состояние x' такое, что число S(x,x')=\sum s_i s'_j максимально. Это не метрика, да.

И ближайших следует читать как "(локально) дальнейших".

Еще нужно добавить в определение S штраф за изменение знака — например, \eps \sum s_i s'_i, где eps<1/(число ребер). Чтобы при одинаковом числе красных и зеленых соседей вершина не меняла цвета.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]flaass@lj
2008-08-08 10:47 (ссылка)
Вот теперь все ОК.
Если, конечно, добавить, что "локально дальнейшее" состояние каждый раз единственно, что правда (после поправки насчет eps).

(Ответить) (Уровень выше)

Re: Errata
[info]flaass@lj
2008-08-08 10:49 (ссылка)
Скрою пока.

(Ответить) (Уровень выше)


(Читать комментарии) -