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

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]_gr_@lj
2008-08-05 10:53 (ссылка)
Зачем ты написал, что она была у нас на сборах?! Я совершенно об этом забыл, и очень обрадовался, что сразу нашел это простое решение...

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


[info]flaass@lj
2008-08-05 10:55 (ссылка)
Пролежало в закромах до нужного момента?:)

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


[info]_gr_@lj
2008-08-05 11:06 (ссылка)
У меня полное впечатление, что я сам только что решил. Но на самом деле, разумеется, вспомнил. Там действительно поучительная идея; такие штуки впечатываются на всю жизнь. Особенно в молодости.

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


[info]flaass@lj
2008-08-05 11:11 (ссылка)
О, заодно покаюсь!
Я тогда очень успешно притворился, что решил ее сам.
На самом деле, когда всем рассказывали решение, а я выходил из класса, чтобы не слышать, самое начало я услышать успел - и этого хватило. Потом перевел его на язык матриц и в нужный момент притворился, что только что придумал :)

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


[info]_gr_@lj
2008-08-05 11:38 (ссылка)
Экий же ты был очковтиратель! Я этот эпизод тоже абсолютно не помню. Вообще, в памяти остались какие-то странные вещи - как я всех в Москве не туда повел и мы опоздали на автобус, как Вадик Книжник приезжал играть в монополию, разговоры с Земляковым про Кима... В общем, только вещи, не относящиеся к делу.

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


[info]flaass@lj
2008-08-06 03:07 (ссылка)
У меня самое яркое воспоминание - чтение наизусть "Луки Мудищева" тем химиком-одесситом, не помню имени.
А, кстати, а ты Библию тогда тоже привез?

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


[info]_gr_@lj
2008-08-06 07:02 (ссылка)
Привез, конечно.

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


[info]flaass@lj
2008-08-06 09:49 (ссылка)
Сейчас понятно, что самое большое достижение тогда было - заиметь личный текст Библии. 77й год, блин.

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


(Анонимно)
2008-08-05 12:22 (ссылка)
Навскидку, нужно задать цвета 1 и -1 и посчитать сумму произведений по всем ребрам. Изменение этого функционала за один шаг задается количеством ребер между теми вершинами, которые изменили цвет и теми, которые не меняли. Поскольку граф конечен, то в конце концов в каждой компоненте связности либо все вершины перестанут менять цвет (период 1), либо все станут его менять на каждом шагу (период 2).

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


[info]botev@lj
2008-08-05 12:56 (ссылка)
есть графы, в которых часть вершин моргают, а часть постоянны.

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


[info]rus4@lj
2008-08-05 12:43 (ссылка)
смену поделили на три группы по уровню

По уровню чего? Я не сумел увидеть в этом разделении какой-либо концепции.

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


[info]flaass@lj
2008-08-05 23:35 (ссылка)
Ее и не оказалось. Приблизительно так: по результатам вступрительной олимпиады, с поправкой на левую ногу.

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


[info]avva@lj
2008-08-05 15:03 (ссылка)
Хорошая задачка. Жаль, что у меня (пока) не получается ее решить :-)
Можно ее дальше передавать? (типа я бы послал на работе в тематическую рассылку итд.)

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


[info]flaass@lj
2008-08-05 23:28 (ссылка)
Можно, конечно. Интересно, как с ней справятся специалисты по собственным значениям матриц смежности :)

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


[info]avva@lj
2008-08-06 04:10 (ссылка)
Ой, я очень надеюсь, что это не подсказка какая-нибудь была :-(

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


[info]flaass@lj
2008-08-06 04:11 (ссылка)
Нет, конечно :)

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


[info]flaass@lj
2008-08-06 04:12 (ссылка)
Хотя вот это, может, и подсказка :)

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


[info]avva@lj
2008-08-06 14:31 (ссылка)
А меняются все светофоры одновременно, я ведь правильно понял? Типа клеточного автомата.

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


[info]flaass@lj
2008-08-06 15:33 (ссылка)
Да, все разом.
И да, как бы клеточный автомат. Только каждая клетка умеет считать до своей степени, а степени могут быть сильно различны.

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


[info]french_man@lj
2008-08-07 12:13 (ссылка)
Изверг:)))

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


[info]french_man@lj
2008-08-07 12:12 (ссылка)
Почему-то вспомнил задачу про парламент, тех же времен (у каждого депутата должно быть не более одного врага:).

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


[info]flaass@lj
2008-08-07 12:26 (ссылка)
В смысле, у каждого не более трех врагов, и их надо рассадить по двум палатам? - Да, хорошая задача, вовсю использую ее в разных версиях.

Вот, кстати, хорошая продвинутая версия (уж сразу на языке графов):

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

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


[info]spamsink@lj
2008-08-07 14:35 (ссылка)
А в направленном графе, где на вершину влияют только соседи по входящим ребрам?

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


[info]flaass@lj
2008-08-08 01:16 (ссылка)
Там любой период можно сделать. Ориентированный цикл, в нем одна красная, остальные зеленые.

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


[info]spamsink@lj
2008-08-08 01:27 (ссылка)
Ну да. Теперь сделаем наблюдение, что два цикла, один из которых может влиять на другой, или стабилизируются, или осциллируют с периодом, равным НОД их длин, и что ненаправленный граф эквивалентен направленному, в котором каждое ребро заменено циклом "туда-сюда" длиной два, и вроде всё.

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


[info]flaass@lj
2008-08-08 01:31 (ссылка)
> сделаем наблюдение
Как его строго сформулировать? (Уж не спрашиваю, как доказать:) )

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


[info]phoonzang@lj
2008-08-07 15:38 (ссылка)
теорема Ф.-П.?

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


[info]flaass@lj
2008-08-08 01:17 (ссылка)
Есть такая. Это специальный ложный след для особо образованных; многие ведутся.

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


[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 (ссылка)
Скрою пока.

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