Представьте себе географическую карту, на которой показана территория распространения какого-либо вида растений или эпидемии. Часть карты, соответствующая этой территории, закрашена определённым цветом, остальная оставлена белой. Чтобы изучить динамику распространения вида или эпидемии, составляют последовательность таких карт, соответствующих различным моментам времени, и пытаются понять закономерности изменения закрашенной части. Если речь идёт об эпидемии, мы, естественно, хотим, чтобы она угасла. Если же речь идёт о каком-то ценном виде, мы хотим, чтобы он сохранился. В обоих случаях нам важно, исчезнет закрашенная часть или нет. Подобные соображения приводят к задачам, аналогичным той, которая была опубликована в 5-м номере нашего журнала за этот год в «Задачнике „Кванта“» (М925). Мы приведём её решение и ещё несколько связанных с ней задач.
М925. На белой плоскости расположена синяя фигура $K_0$. Из неё получается новая синяя фигура $K_1$ по следующему правилу, применяемому одновременно ко всем точкам $M$ плоскости: если не менее половины площади круга радиуса 1 с центром в точке $M$ занято синим цветом, то точка $M$ становится синей, а если менее половины — то белой. На следующем шаге из полученной синей фигуры $K_1$ по тому же правилу получается фигура $K_2$, затем из неё $K_3$ и т. д. Докажите, что:
- для произвольной ограниченной фигуры $K_0$, начиная с некоторого шага, вся плоскость станет белой;
- если $K_0$ — круг радиуса 100, то это случится не позже чем через миллион шагов.
Обозначим буквой $F$ то правило, по которому из каждой фигуры получается следующая. Оно монотонно в следующем смысле: из меньшей фигуры по правилу $F$ получается меньшая; более формально это можно записать так:
$$
K\subset K'\Rightarrow F(K)\subset F(K').
$$
Благодаря этой монотонности, нам достаточно рассматривать в качестве начальных фигур только круги. Действительно, всякая ограниченная фигура лежит в некотором круге, и если уж даже этот круг под действием нашего правила превратится в пустое множество, то содержащаяся в нём фигура — тем более. Круги удобны тем, что под действием $F$ они переходят в круги. Точнее:
- если $K$ — круг радиуса, большего или равного $\dfrac{1}{\sqrt{2}}$ (т. е. площади большей или равной $\dfrac{\pi}{2}$), то $F(K)$ — тоже круг (меньшего радиуса);
- если $K$ — круг радиуса, меньшего $\dfrac{1}{\sqrt{2}}$, то $F(K)$ — пустое множество.
Рассмотрим функцию $f(R)$, определённую при $R$, больших $\dfrac{1}{\sqrt{2}}$, следующим образом: если $R$ — радиус круга $K$, то $f(R)$ — радиус круга $F(K)$. График функции $f$ показан на рисунке 1. Когда $R$ возрастает от $\dfrac{1}{\sqrt{2}}$ до бесконечности, функция $f(R)$ монотонно растёт от $1-\dfrac{1}{\sqrt{2}}$ до бесконечности, причём её график остаётся всё время ниже биссектрисы координатного угла ($R-f(R)\gt0$). Нетрудно доказать, что разность $R-f(R)$ есть монотонно убывающая функция от $R$ (стремящаяся к нулю при $R\to\infty$). Ломаная линия на рисунке 1 показывает, как ведут себя радиусы $R_0$, $R_1=f(R_0)$, $R_2=f(R_1)$, $\ldots$ (на рисунке 1 уже $R_3\lt\dfrac{1}{\sqrt{2}}$, поэтому на следующем, четвёртом шаге получится пустое множество). В общем случае из монотонности $R-f(R)$ следует:
$$
R_0-R_1\lt R_1-R_2\lt R_2-R_3\lt\ldots
$$
Отсюда, обозначая $R_0-R_1=d\gt0$, получим, что $R_n\lt R_0-nd$. Значит, при некотором значении $n$ (не больше чем $\dfrac{R_0}{d}+1$) фигура $K$ будет пуста. Тем самым доказано утверждение а). (В этом доказательстве некоторые детали только намечены, но по ходу приводимого далее решения задачи б) мы получим и ещё одно решение а).)
Чтобы справиться с пунктом б), надо численно оценить величину, на которую уменьшается радиус $R$ круга $K$ под действием правила $F$. Если внутри круга $K$ находится меньшая часть нашего «стандартного» круга $D$ радиуса 1 с центром в точке $M$, то эта точка не входит в $F(K)$, и, следовательно, $f(R)\lt OM$, где $O$ — центр круга $K$. Как видно из рисунке 2, так будет, например, когда окружность круга $K$ пересекает диаметр $AA_1$ круга $D$ в серединах $B$ и $B_1$ радиусов $MA$ и $MA_1$; в этом случае площадь сегмента $BB_1G$ меньше суммы площадей криволинейных треугольников $ABL$ и $A_1B_1L_1$, поэтому площадь пересечения кругов $D$ и $K$ меньше половины площади круга $D$. При этом $OM^2=OB^2-MB^2=R^2-\dfrac{1}{4}$, таким образом,
$$
f(R)^2\lt OM^2=R^2-\dfrac{1}{4}
$$
(при любом $R\gt\dfrac{1}{\sqrt{2}}$), т. е. $R_n^2\lt R_{n-1}^2-\dfrac{1}{4}$.
Отсюда по индукции заключаем, что при $R_{n-1}\gt\dfrac{1}{\sqrt{2}}$
$$
R_n^2\lt R_0^2-\dfrac{n}{4}.
$$
Следовательно, круг произвольного радиуса $R_0$ исчезнет за конечное число шагов (что доказывает утверждение а)), причём это число не больше $4R_0^2+1$. При $R_0=100$ оно заведомо меньше миллиона, что и требуется доказать в задаче 6).
Задачи
1. Пусть $N(R)$ — число применений правила $F$, превращающих круг радиуса $R$ в пустое множество. Мы доказали, что $N\le 4R^2+1$. Докажите, с другой стороны, что $N\ge cR^2$, где $c$ — некоторая положительная константа.
2. Рассмотрим другое правило $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$ — некоторые положительные константы.
3. На белой сфере диаметра $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$?
Рисунок 1
Рисунок 2
