На бесконечной белой плоскости эволюционирует ограниченная черная клякса.
Каждую секунду все точки меняют свой цвет по следующему закону. Чтобы определить
цвет точки в следующий момент времени, надо нарисовать круг единичного радиуса с
центром в этой точке. Если больше половины его площади черная, то центр
становится черным, иначе - белым. Пусть K - клякса, '(штрих) обозначает переход
к следующему моменту времени, Kn означает результат эволюции кляксы
за n единиц времени.
1. а) (А. Тоом) Может ли клякса жить вечно?
б) Может ли ее площадь по сравнению с начальной увеличиться более чем в
миллион раз?
2. Пусть K - клякса, имеющая форму круга радиуса R. Оцените, по
возможности более точно, время ее исчезновения.
Перейдем к исследованию дискретной ситуации. Пусть Z - множество целых
точек на прямой, клякса - произвольное конечное подмножество Z.
Площадь кляксы - число ее точек. Дискретный закон эволюции таков:
фиксируется конечное множество S c Z с нечетным числом элементов и одной
отмеченной точкой (не обязательно из S). S называется шаблоном эволюции.
Чтобы узнать цвет точки x c Z через секунду, надо параллельно перенести
S так, чтобы отмеченная точка перешла в x, и посмотреть, точек какого
цвета шаблон закрывает больше - это и будет цвет точки x через секунду. Будем
называть шаблон убивающим, если любая клякса гибнет при этом
шаблоне, и неубивающим в противном случае.
3. а) Покажите, что если отметить другую точку у шаблона, то каждый
этап новой эволюции будет отличаться от соответствующего этапа старой
параллельным переносом.
б) Существует ли неубивающий шаблон на прямой?
в) Может ли площадь кляксы увеличиться более чем в миллион раз при некотором
шаблоне?
г) Существует ли такой шаблон, содержащий менее ста точек, что площадь любой
кляксы в процессе эволюции увеличивается не более, чем в миллион раз по
сравнению с начальной площадью?
4. Существует ли убивающий шаблон на прямой?
Перейдем к случаю плоскости. Пусть Z2 - множество точек на
плоскости, обе координаты которых целые. Шаблон - это подмножество
Z2, содержащее нечетное число элементов, и одну отмеченную
точку (возможно, не совпадающую ни с одним из этих элементов). Закон эволюции
такой же. Понятия кляксы, убивающего и неубивающего шаблона
вводятся аналогично.
5. Решите задачу 3 для плоскости.
6. Пусть шаблон есть квадрат
а)3*3, образованный 9 узлами решетки;
б)(2n+1)*(2n+1), образованный (2n+1)2 узлами решетки.
Являются ли такие шаблоны убивающими?
7. Существует ли убивающий шаблон на плоскости?
8.а) Исследуйте эволюцию полуплоскости ax+by>c для случая
общего центрально-симметричного шаблона.
б)* Докажите, что всякий центрально-симметричный шаблон на
плоскости - неубивающий.
9.* Докажите, что если шаблон убивающий, то для любого
C > 0 найдется такая клякса, что через некоторое время ее площадь вырастет
более, чем в C раз.
10.* Докажите, что для любого неубивающего шаблона
найдется такое C > 0, что площадь кляксы в процессе эволюции ни за какое время
не может вырасти более, чем в C раз.
11.* Обобщите результаты предыдущих пунктов для
пространственного случая.
12. а) Существуют ли шаблон и клякса такие, что диаметр кляксы в
процессе эволюции неограничен?
б) Верно ли, что путем выбора отмеченной точки (не обязательно внутри
шаблона) можно добиться того, что вся эволюция кляксы будет содержаться внутри
некоторого круга?
13. Существует ли такой шаблон на прямой, что для всякого C > 0
найдется клякса, площадь (число точек) которой вырастает в процессе эволюции
более, чем в C раз? (Кляксы находятся на прямой.)
14. Пусть шаблон сохраняет (не изменяет цвет точек) две полуплоскости
a1x+b1y > c1 и
a2x+b2y > c2, причем прямые
a1x+b1y=c1 и
a2x+b2y=c2 не параллельны. Пусть полуплоскость
a3x+b3y > c3 не сохраняется под действием
этого шаблона. Докажите, что тогда шаблон - убивающий.
15. Пусть шаблон сохраняет все полуплоскости. Докажите, что
он неубивающий.
16. Верно ли, что для всякого убивающего шаблона найдется C > 0,
такое, что время жизни кляксы диаметра d не превосходит C*d.
17. Существует ли такой неубивающий шаблон, что не все его точки
лежат на одной прямой и не являющийся центрально-симметричным?
18. Попробуйте научиться по данному шаблону определять, является ли
он убивающим.
19. Опишите эволюцию кляксы через большое время.
а) Возможна ли непериодическая эволюция?
б) Возможна ли периодическая эволюция?
Если да, то какие могут быть периоды?
20. Обобщите Ваши результаты на n-мерное пространство.
21. Вернемся к непрерывному случаю на плоскости. Пусть шаблон
есть конечное объединение многоугольников и кругов.
б) Верно ли, что любой шаблон - убивающий?
Будем говорить, что при данном шаблоне кляксы имеют линейное время
жизни, если существует константа C > 0 такая, что время жизни любой кляксы
не превосходит C*d. Будем говорить, что кляксы имеют квадратичное время
жизни, если при некотором C > 0 время жизни любой кляксы не превосходит
C*d2, причем найдутся кляксы со сколь угодно большим диаметром, время
жизни которых не меньше C*d2/2. (d всюду обозначает диаметр кляксы.)
б) Верно ли, что для любого шаблона кляксы имеют либо линейное, либо
квадратичное время жизни?
22. а)** Существует ли шаблон, для которого всякая клякса
имеет прообраз?
б)* Тот же вопрос в дискретном случае на плоскости.
23.** (Эта задача предлагалась только участникам, решившим задачу
19.) Дан произвольный шаблон. Исследовать, возможны ли периодические эволюции.
Если возможны, то с какими периодами? Нужно провести классификацию по шаблонам.