Из жизни единиц

31

Из жизни единц
A. Л. Тоом

Увы! — сказал сатурниц,
— мы живем всего лишь пятьсот
больших оборотов Солнца…
Наше существование — точка, срок
нашей жизни — мнновение, наша
планета — atom.

Вольтер. «Микромедас».

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

Известный советский физик Я. И. Френкель говорил, что математическая модель должна быть похожа скорее на карикатуру, чем на «реалистический» рисунок. Основное требование, предъявляемое к модели — это простота: жизньные процессы настояком математики, создать то, что учены наделя подается математическим изучению с трудом. В настоящее время больше популяриность прибрежели так называемые «решчатые модели», описывающие процессы, производящие на решете из одинаковых «клеточек». В таких модели трудности возникют уже тогда, когда каждая клеточка может находиться только в двух состояниях. Об этом мы и рассказем в статье.

1. Колонии и операторы

Для математika клетчатая бумага tant в себе много привлекательных возможностей. Воспользуемся здесь одной из них. Откройте страницу тетради в клетку. Вы видите на ней сетку из вертикальных и горизонтальных линей. Точки их пересечения будем для краткости называть узлами. Представим себе мир, который только из всех этих узлов и состоит. Правда, страницу при этом вообразим бесконечной. Пусть в этих узлах могут жить с щетва: edиницы. На рисунках единцы будем обозначать жирными точками, как на рисунке 1. В каждом узле может находиться одновременного только одна единца, а если в узле нет единцы, то там стоит нуль. Совокупность всех узлов, заятых единцами, будем назвать колоней. Если единц конечное число, то колоню называет конечной. Если нет ни одной единцы, то мы скажем, что у нас пустая колоня. (Время, как и пространство, дискретно. Это значит, что оно нумеруется целыми числами: 0, 1, 2,…) Должен быть задан оператор P, то есть п ра в и л о, которое для любой колонии K, существуют в некоторых момент времени t, определяет, какая из нее получится колония PK в следующий момент времени t + 1.

Пусть такой оператор P задан. Основной вопрос, который мы попытаемся выяснить, таков. Существует ли для данного оператора P бессмертная конечная колония, то есть макая конечная колония K, что, сколько бы раз ни применять к ней оператор P, всегда будет получаться неусмотряя колония? Или же набором, оператор P может, что всякая конечная колония через некоторое время вымирает, то есть не остается ни одной единцы?

Разберем сначала два примера. Введем координаты оси, взяв за начало координат O один из узлов и направив, как обычно, ось абсцисс вправа, ось ordинат вверх (см. рис. 1) и приняв сторону клетки за единцу.

32

Пример 1. Пусть в момент $t + 1$ в узле $A = (x, y)$ будет единица в том и только в том случае, если в момент $t$ единицами было занято больше и иствою из пятей узлов: этого узла $A$ и четырех соседних с ним: справа $(x + 1, y)$, слева $(x - 1, y)$, сверху $(x, y + 1)$ снизу $(x, y - 1)$. Оператор $P$ задан.

Упражнение 1. Что порождают колонии, изображенные на рисунке 1 («жирные» точки и крестики), под действием этого оператора? Проследите дальнейшую эволюцию колонии. Существует ли для этого оператора бессмертная конечная колония?

Пример 2 (см. задачу M215). Пусть в момент $t + 1$ в узле $A = (x, y)$ будет единица тогда и только тогда, если в момент $t$ единицами было занято больше и иствою из трех узлов: этого узла $A$ и двух соседних: справа $(x + 1, y)$ и сверху $(x, y + 1)$. Оператор $P$ задан.

Из решения задачи M215 (опублікованного в «Кванте» № 3, 1974) следует, что под действием этого оператора всякая конечная колония вымирает. (Проверьте это для колонии на рис. 1). Докажем этот факт еще раз способом, который пригодится нам в дальнейшем.

Изучим эволюцию колониий специального вида, заполняющих равноведенный прямогольный треугольник с катетами, направленных вправо и вверх от вершины прямого угла (рис. 2). Оказывается, какый такой треугольник в следующий момент времени переходит в треугольник такого же вида, но с меньшей на единицу длиной катетов. Только самый маленький треугольник с длиной катетов 1 переходит в одну точку, а она на следующем шаге пропадает. (Проверьте это, проследив эволюцию рисунка 2.) Поэтому какый такой треугольник вымирает за время, равное первоначальной длине катетов.

Пусть теперь у нас есть произвольная конечная колония $K$. Ее можно заключить в равноведенный прямогольный треугольник, что и сделано на рисунке 3. Тогда колония, получающаяся из нее в следующий момент, будет помещаться внутри меньшего треугольника такого же вида, и так далее.

Здесь мы воспользуемся важным свойством оператора $P$: если колония $K_1$ есть часть колонии $K_2$ (это можно записать так: $K_1 \subset K_2^*$), то $PK_1$ есть часть $PK_2$: $PK_1 \subset PK_2$ (что не исключает возможность, что $PK_1$ и $PK_2$ совпадают). Наозем это свойство, которое коротко можно записать так:

$$K_1 \subset K_2 \Rightarrow PK_1 \subset PK_2,$$

монotonность оператора $P$. В этой статье рассматривается только monotonные операторы.

Для немонotonных операторов воросо том, когда существует бессмертные конечные колонии, в общем виде не решен и, возможно, очень труден. Интересный и общий материал об исследовании одного конкретиного немонotonного оператора, получившего название игры «Жизнь», собран в книге М. Гарднер «Matematические досуги» (глава 38). Познакомиться с этой игрой вы можете на с. 26 этого номера журнала.

Опишем теперь точно, какого вида оператора $P$ мы будем рассматривать.

*) Знак $\subset$ означает включение множества. Мы будем дальнейшее пользоваться также понятными пересечениями, объединениями и дополнениями множества (об операциях над множествами см., например, статью С. Г. Гиндин и «Сколько существует операция над множествами», «Квант», 1973, № 7).

33

Пусть $O$ — «нулевой» узел, начало координат. В описание $\mathbf{P}$ входит список $\mathbf{U}$, состоящий из $r$ узлов $u_1, \dots, u_r$, от состояний которых в момент $t$ зависит состояние узла $O$ в момент $t + 1$. В примере 1 число этих узлов $r = 5$, в примере 2 $r = 3$. Состояние любого узла $A$ в момент $t + 1$ зависит от состояния узлов $A + u_1, \dots, A + u_r$ в момент $t$. Знак + здесь означает сложение векторов. Например, если $A = (x, y), u_1 = (x', y')$, то $A + u_1 = (x + x', y + y')$.

Упражнение 2. Напишите координаты векторов $u_1, \dots, u_5$ в примере 1 и векторов $u_1, u_2, u_3$ в примере 2.

Кроме списка $\mathbf{U}$, в задании оператора $\mathbf{P}$ входит функция, определяющая как именно зависит состояние узла $A$ в момент $t + 1$ от состояния узлов $A + u_1, \dots, A + u_r$ в момент $t$. Чтобы задать такую функцию, нужно указыть, что будет в узле $A$ в момент $t + 1$ — единица или же нуль — для каждого комбинации единиц и нулей в узлах $A + u_1, \dots, A + u_r$ в момент $t$. Всего таких комбинаций $2^r$. Можно, например, составить таблицу, в которой против каждой комбинации из единиц и нулей поставить либо единицу, либо нуль, что и сделано на рисунке 4 (проверьте, что функция, заданная этой таблицей, определяет оператор $\mathbf{P}$ из примера 2).

| Состояния узлов | В момент $t$ | $t + 1$ |
| :— | :— | :— |
| $(0,0)$ | $(0,1)$ | $(1,0)$ | $(0,0)$ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

Рис. 4.

Составлять таблицу, конечно, не обязательно, можно функцию задать сложенно, но так, чтобы по сложному заданию можно было бы однозначно составить такую таблицу.

Функции $f = f(a_1, a_2, \dots, a_r)$, аргументы и значения которых принимают только два значения, 0 и 1, называются булевскими или двойными. Булевская функция называется monotonной, если из

$$a_1 \leqslant a'_1, \dots, a_r \leqslant a'_r$$

следует

$$f(a_1, \dots, a_r) \leqslant f(a'_1, \dots, a'_r).$$

Как уже говорилось, мы будем рассматривать только монotonные операторы. Они задаются монotonными функциями. Положим, кроме того, $f(0, \dots, 0) = 0$, $f(1, \dots, 1) = 1$.

Эти ограничения не существует, поскольку не удовлетворяют им из монotonных функций только константы — функции, принимающие только одно значение (всегда нуль или всегда единицу). Функции - константы очень просты, и поэтому неинтересны.

Пример 3. Пусть в момент $t + 1$ в узле $A = (x, y)$ будет нуль в том и только в том случае, если в момент $t$ выполняется хотя бы одно из двух условий:

a) нули стояят в общих узлах $(x, y)$ и $(x, y + 1)$;
b) нули стояят в общих узлах $(x + 1, y)$ и $(x + 1, y + 1)$.

Оператор $\mathbf{P}$ задан.

Упражнение 3. a) Проследите эволюцию колонни, изображенных на рисунке 1, под действием этого оператора.

Неправда ли, создается впечаление, что колонни сплошивают с правого бока, но заговляется впечаление?

b) Доказите, что под действием оператора примера 3 всякая конечная колоння вымирает.

Пример 4. Пусть в момент $t + 1$ в узле $A = (x, y)$ будет нуль тогда и только тогда, если в момент $t$ выполняется хотя бы одно из двух условий:

a) нули стояят в общих узлах $(x, y)$ и $(x + 1, y + 1)$;
b) нули стояят в общих узлах $(x + 1, y)$ и $(x, y + 1)$.

Оператор $\mathbf{P}$ задан.

34

Рис. 5. Рис. 6.

Для этого оператора существуют беспетрные конечные колонии, правда, все время изменяющиеся, но никака не вымирающие. Найдите какую-нибудь из них.

2. Нульевые множества.
   Теорема о выживании

Вспомним теперь, что на плоскости, кроме узлов, есть еще и другие точки. Конечно, с точки зрения единниц, живущих только в узлах, никаких других точки в природа не существует, но для нас-то они существуют. Будем рассматривать всевозможные геометрические фигуры — множества точки на плоскости. Скажем, что фигура М заполнена нулями, если нули стоит во всех узлах, принадлежих этой фигуре.

Определение 1. Фигура М называется нулявой (для данного оператора P), если из мою, что она заполнена нулями в момент t, следуем, что в узле O будет нуль в момент t + 1.

Так, в примерах 1, 2 фигура является нулявой, если она содержит большинство из пяти — в примере 1 — или трех — в примере 2 — узлов, составляющих множество U.

Пусть на плоскости проведена прямая l. Изовем полупоскстью множество точки, расположенных по одному сторону от прямой, включая саму эту прямую.

В соответствии с определением 1 полупосксть называется нулявой, если из того, что она заполнена нулями в момент t, следует, что в узле O будет нуль в момент t + 1.

Обозначим через σₚ пересечение всех полупоскостей, нулявых для данного оператора P.

Теорема о выживании. Под действием оператора P всякая конечная колония вымирает модель и molъко мода, если множество σₚ пусто.

Уражнение 4. (Проверка теоремы для примеров 1—4.) Доказайте следующие утверждения.

a) В примере 2 три полупоскости, защищенных на рисунке 5, являются нулями. В примере 3 две полупоскости, защищенных на рисунке 6, являются нулями.

В обихах случае защищенные полупоскости не имеют общих точки, то есть их пересечение пусто. Поэтому σₚ — пересечение всех нулявых полупоскостей тем более пусто. В соответствии с теоремой все конечные колония вымирают.

b) В примере 1 множество σₚ состоит из одной точки O (и в соответствии с теоремой, существует беспетрная конечная колония).

В примере 4 множество σₚ состоит из одной точки ξ = (1/2, 1/2). (Точка ξ — не узел. Вот почему нам не хватило узлов!)

В примере 1 точки O входит в σₚ, а конечная беспетрная колония остается на месте. В примере 4 простейшая беспетрная колония состоит из четырех узлов — вершин одного единчного квадрата (рис. 7). В следующий момент времени она порождает «крест», а этот крест в свою очередь такой же квадрату, но сдиинутий

35

на единицу влево и вниз. Складем, что колония $K$ заполняет фигуру $M$, если она содержит все узлы, входящие в $M$. И крест, и квадратик на рисунке 7 можно представить как колонии, заполняющие равные фигуры — квадраты, показанные на этих рисунках. Таким образом, колонии, порождаемые в последовательные моменты времени, можно представить как заполняющие один и тот же квадрат, сдигασищей за единицу времени на вектор $-\vec{\xi} = \left(-\frac{1}{2}, -\frac{1}{2}\right)$. Заметим, что стороны этого квадрата параллельны прямым $u_i$ и $\xi$, где $u_i \in U$. В примере 1 стороны единичного квадрата, заполняемого колонией, также параллельны линям $u_i O$.

У праванние 5 (изделательское) Если бы были единичей и жили бы в мире, управляемом оператором примера 4, то существовала бы для вас точка $\xi = \left(\frac{1}{2}, \frac{1}{2}\right)$ или нет?

3. Выпуклы множества и выпуклы оболочки

Множество точек $M$ на плоскости называется выпуклым, если удовлетворяет следующему условия:

если точки $A$, $B$ принадлежат $M$, то и все точки отрезка с концами $A$, $B$ принадлежат $M$.

У праванние 6. Доказите, что всякая полуплоскость — выпуклое множество.

У праванние 7. Доказите, что пересечение нескольких выпуклых множества — выпуклое множество.

У праванние 8. В некоторых условиях многоугольник называется выпуклым, если он расположен по одному сторону от прямой, проведенной через каждой его сторону. Доказите, что многоугольник будет выпуклым в этом смысле тогда и только тогда, когда выпуклое множество точек, расположенных на его контуре и внутри него.

Итак, если выпуклое множество $M$ содержит точки $A_1, \dots, A_h$, то оно содержит также и все отрезки с концами в этих точках, и все треугольники с вершинами в этих точках. Обедининие всех точек $A_1, \dots, A_h$ на плоскости, отрезков с концами в этих точках и треугольников с вершинами в этих точках называется выпуклой оболочной точек $A_1, \dots, A_k$ (на рисунке 8 выпуклая оболочка точек $A_1, \dots, A_k$ закрашена). Можно сказать, что выпуклая оболочка точек $A_1, \dots, A_k$ — это то, что обязаетлено входить в все коеев выпуклое множество, содержащие точки $A_1, \dots, A_k$.

У праванние 9. а) Доказите, что множество, состоящее из четырех точек (на плоскости), всегда можно разбит на два подмножества, выпуклые оболочки которых пересекаются.

6. То же, если множество состоит из $n > 4$ точек.

Вспомним определение множества $\sigma_P$. Если искать $\sigma_P$, следует этому определению, то придется строить все нульевые полуплоскости, а их бесконечно много. Правда, в примерах 1—4 мы суммали найти $\sigma_P$, но пока не ясно, как сделать это в общем случае. Оказываться, с помощью выпуклых оболочных можно строить $\sigma_P$ уже для любого оператора $P$.

Рассмотрим все подмножества $U$. В соответствии с определением 1, множество $U' \subset U$ называется нульевым, если из того, что $U'$ заполнен нульями в момент $t$, следует, что в точке $O$ будет нуль в момент $t + 1$.

Лемма 1. Множество $\sigma_P$ совпадает с пересечением выпуклых оболочных всех нульевых подмножества $U$.

Доказите эту лемму самостояльно. Указан ие. Полуплоскость является нульевой тогда и только тогда, когда она содержит целиком хотя бы одно нульевое подмножество $U$.

Пользовать леммо 1, можно по всякому оператору $P$, заданному набором $U$ и функцией $f$, построить $\sigma_P$. Именно, надо выписать все подмножества $U$ (их $2^r$ штук), далее, зная функцию $f$, выбрать из них нульевые, построить их выпуклы

37

Рис. 12.

после $t$ применений оператора $P$ согласно следующим замечанием и из-заedom будут заполнены нулем и из-заedom будут заполнены нулем полуплоскости, получающие из $\Pi'_1, \Pi'_2, \Pi'_3$ сдвиги на $t v_1, t v_2, t v_3$; при $t \geq d$ эти полуплоскости тем более покройот всю плоскость. Значит, все плоскость будет заполнена нулем, а это и означает, что колония $K$ вымирает.

Лемма 3. Пусть две полуплоскости, ограниченные двумя параллельными прямыми и расположенные по внешние стороны от них, являются нулевыми для оператора $P$ (как на рис. 6). Тогда под действием этого оператора всякая конечная колония единц вымирает.

Докажите эту лемму самостоятельно. Указан ие. Обобщите решение упражнения 3.

Леммы 2 и 3 можно обединить в одно следующое утверждение:

Лемма 4. Если пересечение трех нулевых полуплоскостей пусто, то всякая конечная колония единц вымирает.

Доказательство. Если пересечение трех полуплоскостей пусто, то либо они расположены как на рисунке 10, либо какое-то две из них расположены как на рисунке 6, а для этих двух случав утверждение леммы 4 доказано.

Б. Пусть теперь множество $\sigma_p$ содержит хотя бы одну точку. Докажем, что тогда существует конечная бескмерная колония.

Лемма 5. Пусть бесконечная колония $K$ заполняется $t$ полуплоскость $\Pi$, имеющую хотя бы одну общую точку с множеством $\sigma_p$. Тогда колония $PK$ содержит узел $O$.

Доказательство. Допустим, что $PK$ не содержит $O$. Значит, в момент $t + 1$ в точке $O$ стоит 0, то есть в момент $t$ какое-то нулевое подмножество $U$ было целиком заполнено нулями. Значит, это нулевое подмножество не имело ни одной общей точки с $\Pi$, то есть принадлежало дополнительно к $\Pi$. Но дополнительное к $\Pi$ — выпуклое множество. Поэтому выпуклая оболочка этого нулевого подмножества тоже целиком принадлежала дополнительно к $\Pi$. Значит, (см. лемму 1) и $\sigma_p$ целиком принадлежало дополнительно к $\Pi$, что противоречит условиями.

Следствие. Пусть бесконечная колония $K$ заполняется полуплоскость $\Pi$, имеющую хотя бы одну общую точку с множеством $A + \sigma_p$, где $A$ — узел. Тогда колония $PK$ содержит узел $A$.

Основной для случая Б является Лемма 6. Пусть точка $\xi$ принадлежит $\sigma_p$ (как точка $(1/2, 1/2)$ в примере 4). Тогда существует такой выпуклый многоугольник $M$, что, если колония $K$ заполняется $M$, то колония $PK$ заполняется многоугольник $M - \vec{\xi}$ (рис. 12), колония $P^2 K$ заполняется $M - 2\vec{\xi}$ и так далее; вообщее, колония $P^n K$, получаемая из $K$ через $n$ моментов времени, заполненное многоугольник $M - n\vec{\xi}$, равный $M$ и полученный из $M$ свызом на вектор $-n\vec{\xi}^*$). При этом все колония $K$, $PK$, $P^2 K$, … непусты.

*) Мы утверждаем, что единцами заняты все узлы, принадлежащие $M - n\vec{\xi}$ но, возможно, не только они: не исключено, что единцы будут и вне этого мнестоугольника.

38

Из этой леммы, в частности, следует, что если точка $O$ принадлежит $\sigma_p$, то существует «стабильная» колония, не теряющая в процессе эволюции ни одного своего узла (но, возможно, прибретающая новые).

Доказательство. Заметим, что мы не претендуем на то, чтобы найти наименьшую бессмертную колонию (как мы нашли для примеров 1 и 4). Нам достаточно найти какую-нибудь. Поэтому будем с самого начала считать многоугольник $M$ очень большим. Каким точно, скажем ниже.

Утверждение леммы достаточно доказать только для $n = 1$; для больших $n$ это будет следовать по индукции. Итак, предположим, что колония $K$, существующая в момент $t$, заполняется $M$; доказем, что колония $PK$ заполняется многоугольник $M - \xi$.

Пусть какой-то узел $A$ принадлежит $M - \xi$ (см. рис. 14). Покажем, что $A$ принадлежит $PK$ (это записьют так: $A \in PK$). Очевидно, $(A + \xi) \in M$. Обозначим через $R$ наиболее из расстояний от точки $\xi$ до узлов $u_1, \dots, u_r$. Тогда круг с центром $A + \xi$ и радиусом $R$ накроет все узлы $A + u_1, \dots, A + u_r$. Выберем $M$ столбцы, чтобы всякий круг с центром внутри $M$ принадлежа $R$ либо ввобше не накрывал точок сторона многоугольника $M$, либо накрывал точки лишь одной стороны $M$, либо накрывал точки лишь двух соседних сторон, но не больше. (На рисунке 13 изображен круг, накрывающий точки трех сторон треугольника — такого быть не должно!) Расмотрим три случая.

a) Круг с центром $A + \xi$ радиуса $R$ помещается целиком внутри $M$ (см. рис. 14). Тогда все узлы $A + u_i$ тем более внутри $M$, то есть они входят в $K$; значит, узел $A$ входит в $PK$.

b) Круг с центром $A + \xi$ и радиусом $R$ накрывает точки только одной из сторон $M$ (как на рисунке 15). Проведем прямую $l$ через эту сторону. Если колония $K$ заполняется все полуплоскость $\Pi$, ограниченной $l$ (на рисунке 15 эта полуплоскость защитыхована), то колония $PK$ содержаiba бы узел $A$ по следствию из леммы 5 (полуплоскость $\Pi$ содержит точку $A + \xi$, и поэтому пересекается с множеством $A + \sigma_p$). Но колония $PK$ будет содержать узел $A$ и в том случае, если $K$ заполняет только $M$, так как состояние узла $A$ в момент $t + 1$ зависит только от состояния узлов $A + u_i$ в момент $t$, а эти узлы не входят в разность между $\Pi$ и $M$.

b) Круг с центром $A + \xi$ радиуса $R$ накрывает точки двух соседних сторон $M$ (см. рис. 16). Мы хотим доказать, что для того, чтобы в узле $A$ в момент $t + 1$ была единица, достаточно чтобы в момент $t$ единицы были в тех точках

39

Рис. 16.

$A + u_1, \dots, A + u_r$, которые попадают в область пересечения $M$ с кругом. Мы докажем, что на самом деле для этого достаточно наличия единиц даже в меньшей области — пересечения того же круга с многоугольником $M'$, полученным из $M$ таким сдигром, при котором обшая вершина двух соседних сторон $M$, часть которых накрыта кругом, попадает в точку $A + \xi$ (рис. 16). Для этого нам потребуется наложить на $M$ еще одно, теперь уже последнее, условия.

Проведем прямые через точку $\xi$ и каждой из узлов $u_1, \dots, u_r$, отличных от $\xi$ (если все $u_i$ отличны от $\xi$, то получится $r$ прямых; если один из них совпадает с $\xi$, то получится $r - 1$ прямая). Потрёбут, чтобы для каждой из этих ($r$ или $r - 1$) прямых нашли две стороны многоугольника $M$, ей параллельные. Тогда каждой прямой, параллельная прямой, проходящей через $\xi$ и кakyонибудь из точки $u_1, \dots, u_r$, отличных от $\xi_2$ либо вовсе не пересекает $M$, либо имеет с $M$ целый общий отрезок. Этому условия, например, удовлетворяет квадрат на рисунке 7 (пример 4).

Проведем теперь через точку $A + \xi$ прямую $l$, имеющую с многоугольником $M'$ лишь одну общую точку $A + \xi$ (см. рис. 16). Если только $K$ заполняется всю популское $\Pi$, ограниченную прямой $l$ (на рисунке 16 она затрихована сининим), то по следствию леммы 5, в точке $A$ в момент $t + 1$ была бы единица. Но колония $PK$ будет содержать узел $A$ и в том случае, если $K$ заполняет только $M$, поскольку узлов $A + u_i$, лежащих в популское $\Pi$, но вне $M'$, — нет. Доказем это. Допустим, что какой-то узел $A + u_i$ оказывается в разности между $\Pi$ и $M'$. Но в то же время он находится в круге с центром $A + \xi$ радиуса $R$. Значит, узел $A + U_i$ лежит в одном из двух секторов, заштрихованных черным. Тогда прямая, проходящая через $A + u_i$ и $A + \xi$, имеет $C'$ лишь одну общую точку, что невозможно в силу выбора $M$. Тем самым лемма 6 доказана.

В. Теорема Хелли. Итак, мы исследовали также два случая:

A) пересечение каких-то трех нулевых популское пусть (lemma 4);

B) пересечение всех нулевых популское пусть (lemma 6).

Оказывается, только эти случая и возможности. Это следует из известной теоремы Хелли.

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

Теорема Хелли. Пусть на плоскости имеется $n \geq 4$ выпukых множества, какые при из которых имеются общую точку. Тогда все эти $n$ множества имеются общую точку.

Приименим ее к нашему случае. По следствию из леммы 1 можноесто $\sigma_p$ есть пересечение конечного числа популское пусть, а это и есть случая $A$. Тем самым теорема о выживании доказана.