Текст статьи Тоом А. Л. Кляксы на плоскости // Квант. — 1985. — № 9. — С. 47—48.
Представьте себе географическую карту, на которой показана территория распространения какого-либо вида растений или эпидемии. Часть карты, соответствующая этой территории, закрашена определённым цветом, остальная оставлена белой. Чтобы изучить динамику распространения вида или эпидемии, составляют последовательность таких карт, соответствующих различным моментам времени, и пытаются понять закономерности изменения закрашенной части. Если речь идёт об эпидемии, мы, естественно, хотим, чтобы она угасла. Если же речь идёт о каком-то ценном виде, мы хотим, чтобы он сохранился. В обоих случаях нам важно, исчезнет закрашенная часть или нет. Подобные соображения приводят к задачам, аналогичным той, которая была опубликована в 5-м номере нашего журнала за этот год в «Задачнике „Кванта“» (М925). Мы приведём её решение и ещё несколько связанных с ней задач.
М925. На белой плоскости расположена синяя фигура
- для произвольной ограниченной фигуры
$K_0$, начиная с некоторого шага, вся плоскость станет белой; - если
$K_0$ — круг радиуса 100, то это случится не позже чем через миллион шагов.
Обозначим буквой
Благодаря этой монотонности, нам достаточно рассматривать в качестве начальных фигур только круги. Действительно, всякая ограниченная фигура лежит в некотором круге, и если уж даже этот круг под действием нашего правила превратится в пустое множество, то содержащаяся в нём фигура — тем более. Круги удобны тем, что под действием
- если
$K$ — круг радиуса, большего или равного$\dfrac1{\sqrt2}$ (т. е. площади большей или равной$\dfrac\pi2$), то$F(K)$ — тоже круг (меньшего радиуса); - если
$K$ — круг радиуса, меньшего$\dfrac1{\sqrt2}$, то$F(K)$ — пустое множество.
Рассмотрим функцию
Чтобы справиться с пунктом б), надо численно оценить величину, на которую уменьшается радиус
Следовательно, круг произвольного радиуса
Задачи
- Пусть
$N(R)$ — число применений правила$F$, превращающих круг радиуса$R$ в пустое множество. Мы доказали, что$N\le 4R^2+1$. Докажите, с другой стороны, что$N\ge cR^2$, где$c$ — некоторая положительная константа. - Рассмотрим другое правило
$H$ преобразования фигур на плоскости. Введём систему координат$Oxy$. Если дана фигура$K$, то новая фигура$H(K)$ состоит из всех точек$T(x;y)$, для которых пересечение$K$ и треугольника с вершинами$(x;y)$, $(x+1;y)$, $(x;y+1)$ имеет площадь, не меньшую половины площади этого треугольника. Докажите, что всякая ограниченная фигура под многократным действием$H$ превращается в пустое множество за конечное число шагов$N$, причём для круга радиуса$R$ $$ c_1\cdot R\le N\le c_2\cdot(R+1), $$ где$c_1$ и$c_2$ — некоторые положительные константы. На белой сфере диаметра
$d\gt1$ задана синяя фигура$K_0$. Сопоставим каждой точке$M$ сферы её «окрестность»$D_M$ — часть сферы, заключённую в шаре диаметра 1 с центром$M$, и образуем новую синюю фигуру$K_1$ из тех и только тех точек$M$, для которых площадь пересечения$D_M$ и$K_0$ не меньше половины площади окрестности$D_M$. Аналогично из$K_1$ получается$K_2$ и т. д.- Докажите, что если исходная фигура
$K_0$ содержится в шаре диаметра, меньшего$d$, то через конечное число шагов вся сфера станет белой. - Докажите, что для любого
$\epsilon\gt0$ можно указать такое$d$ и такую синюю фигуру$K_0$ площади не больше$\epsilon\pi d^2$ на белой сфере диаметра$d$, что после конечного числа описанных превращений вся сфера станет синей. - Существуют ли отличные от полусферы фигуры
$K_0$, для которых$K_1$ совпадает с$K_0$?
- Докажите, что если исходная фигура