Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 27 из 31

, и находятся в общем положении?
а) При любых б) При любых ϕ, кроме ϕ = 2πk/3, где k — целое.
в) При любых ϕ, кроме ϕ = πk/3, где k — целое.
г) Ни при каких ϕ.
a
)
б
)
в
)
Рис. 2
II. Требуется так покрасить три вершины октаэдра в белый цвета три другие — в черный, чтобы после небольшого шевеления этих вершин треугольник с вершинами в белых точках был бы зацеплен с треугольником с вершинами в черных точках. Выберите все способы раскраски вершин на риса, б, в, которые удовлетворяют данному условию. Сколько существует зацепленных разделенных пар для шестерки точек из примера а) б) в) 2.

Гл. 14. Комбинаторная геометрия. Докажите, что четность зацепленности не зависит от выбора шестерки точек. Приведите пример шестерки точек, зацепленность которой равна. Докажите теорему 1.
2. Вписанные узлы и зацепления
Основные понятия. Узел можно представлять себе как веревку,
концы которой соединены. Веревку будем считать эластичной, и узлы, получающиеся друг из друга деформацией
4)
веревки, различать не будем.
Примеры различных узлов тривиальный K, правый и левый трилистники, восьмерка E (рис. Если взять не одну веревку, а несколько, и у каждой из них соединить концы, то получим зацепление.
Примеры различных зацеплений зацепление Хопфа H, двойное зацепление, зацепление Уайтхеда W , кольца Борромео B (рис. 4).
2.1. В какие из узлов и зацеплений, изображенных на рис. 3 и можно продеформировать узлы и зацепления на рис. Определение (вписанного узла и зацепления. Пусть в пространстве дано некоторое множество точек и узел. Если веревку продефор- мировать в ломаную, все вершины которой принадлежат данному множеству, то получится узел, вписанный в данное множество точек. (При этом часть точек множества может остаться незадействованной) Будем говорить также, что полученная ломаная образует данный узел.
Аналогично определяется вписанное зацепление.
Зацепление. Если каждую точку множества соединить прямолинейным отрезком с каждой из остальных точек, то вписанный узел является подмножеством полученной фигуры.
Сформулируйте теорему Негами (см. начало статьи) с помощью введенных понятий. Попробуйте доказать эту теорему для трилистника.
Указания, а также связанные с этой теоремой открытые вопросы будут даны в последующих частях этой статьи.
Контрольный вопрос. Какой узел представляет ломаная, вписанная в множество из точек, проекция которой изображена на риса) К;
б) Тп;
в) Тл г) Ед) такой ломаной не существует.
4)
В процессе деформации запрещается разрывать веревку (концы веревки также должны оставаться соединенными веревка, разумеется, не может самопересе- каться.

Теория Рамсея для зацеплений
425
K
Tп
Tл
E
Рис. Рис. 4
а)
б )
в)
г)
д )
е)
Рис. 5

Гл. 14. Комбинаторная геометрия. Докажите, что всякий узел, вписанный в набор из 6 5 точек,
тривиален.
Рис. 6 2.3. Приведите наборы с минимальным числом точек, в которые можно вписать:
а) зацепление Хопфа;
б) кольца Борромео;
в) трилистник;
г) двойное зацепление;
д) восьмерку;
е) зацепление Уайтхеда.
(Доказывать минимальность необязательно. Зацеплены ли а) два треугольника, образующих зацепление Хопфа;

б) два из трех треугольников, образующих кольца Борромео?
3*. Зацепленные четырехзвенные ломаные
Теорема 1
′
(Закс, 1981). Пусть в пространстве даны 4 красные и 4 синие точки, причем никакие два отрезка с разноцветными концами не имеют общих внутренних точек. Тогда найдутся две зацепленные замкнутые четырехзвенные ломаные с вершинами в этих точках, звенья которых соединяют точки разных цветов. На плоскости даны три синие и три красные точки, причем никакие три точки не лежат на одной прямой. Докажите, что найдутся два отрезка с разноцветными концами, пересекающиеся во внутренней точке.
Определение коэффициента зацепления четырехзвенных ломаных. Пусть  и 
′
— две замкнутые четырехзвенные ломаные в пространстве, с вершинами A, B, C, D и A
′
, B
′
, C
′
, соответственно, находящимися в общем положении. Их коэффициентом зацепления lk(ABCD, A
′
B
′
C
′
D
′
) назовем остаток при делении на 2 количества точек пересечения контура ABCD с объединением треугольников и A
′
D
′
C
′
3.2. Докажите, что lk (ABCD, A
′
B
′
C
′
D
′
) = lk(ABCD, B
′
C
′
D
′
A
′
).
3.3. Решите аналоги задач 1.4–1.6 для четырехзвенных ломаных. Заменим требование общего положения более слабым требованием. Дайте для этого случая определение коэффициента

Теория Рамсея для зацеплений
427
зацепления четырехзвенных ломаных так, чтобы сохранились предыдущие свойства.
Определение (общего положения в случае двух цветов. Набор точек в пространстве, окрашенных в два цвета, называется набором общего положения, если никакие два отрезка с разноцветными концами не имеют общих внутренних точек.
Определение (разделенной пары четырехзвенных ломаных).
Пусть в пространстве дан набор 4 красных и 4 синих точек общего положения. Назовем разделенной парой две замкнутые четырехзвен- ные ломаные со следующими свойствами (1) их вершины расположены в данных точках (2) они не имеют общих вершин (3) их звенья соединяют точки разных цветов.
Контрольные вопросы I. Имеется набор точек, в котором есть хотя бы 3 синие и хотя бы 3 красные точки. Пусть все синие точки лежат на прямой a, а все красные — на прямой b. В каких случаях данный набор будет набором общего положения?
а) Никогда.
б) Если прямые a и b скрещиваются.
в) Если прямые a и b не параллельны.
г) Всегда.
a
)
б
)
в
)
Рис. 7
II. Требуется так покрасить четыре вершины куба в белый цвета четыре другие — в черный, чтобы после небольшого «шевеления»
этих вершин можно было выбрать замкнутую четырехзвенную ломаную с вершинами в белых точках и замкнутую четырехзвенную ломаную с вершинами в черных точках, зацепленную с ней. Выберите все способы раскраски вершин на риса, б, в, которые удовлетворяют данному условию

Гл. 14. Комбинаторная геометрия
Рис. 8
III. Найдите коэффициент зацепления двух че- тырехзвенных ломаных, образующих двойное зацепление (риса) б) в) г) зависит от способа, каким двойное зацепление вписано в набор из 8 точек. Пусть 4 красные точки лежат на одной прямой, а 4 синие — на другой прямой, скрещивающейся с ней. Найдите в этом случае все разделенные пары (, 
′
), для которых lk(, 
′
) = 1.
3.6. Дайте определение зацепленности для четверки синих и четверки красных точек и докажите,
что она четна. Докажите теорему 1
′
3.8. Докажите, что в предположениях теоремы найдутся хотя бы две пары зацепленных замкнутых четырехзвенных ломаных. Доказательство теоремы Негами для трилистника
Определение (узла (зацепления, вписанного в раскрашенное множество. Пусть в пространстве дано множество точек, окрашенных в два цвета. Тогда под вписанным узлом будем понимать ломаную,
образующую данный узел, звенья которой соединяют точки разных цветов. Вписанное зацепление определяется аналогично (ср., например,
с теоремой Теорема 2
′
(Ми¨ечи, 1994). Для любого узла (зацепления) найдется такое число N, что в любое множество N синих и N красных точек в пространстве, никакие 4 из которых не лежат водной плоскости, можно вписать данный узел (зацепление).
Очевидно, теорема Негами следует из теоремы Ми¨ечи.
Определение (положительного набора. Пусть в пространстве дан набор N синих и N красных точек, находящийся в общем положении
(смотри определение выше. Проведем все отрезки, соединяющие точки разного цвета. Зафиксируем некоторую плоскость, которую будем считать расположенной горизонтально. Нарисуем на ней проекцию полученной фигуры. В дальнейшем нас будет интересовать только эта плоская картинка и мы будем говорить точка набора и «отрезок»,
подразумевая соответственно проекция точки набора и проекция проведенного нами отрезка».
Пусть точки набора не попадают внутрь отрезков. В каждой точке пересечения отрезков (перекрестке) укажем, какой из отрезков проходит выше (как в задаче 1.6). Назовем перекресток положительным

Теория Рамсея для зацеплений
429
(рис. 9 слева, если при движении по отрезку, который проходит выше,
от синего конца к красному синий конец другого отрезка остается слева.
Иначе перекресток назовем отрицательным (рис. 9 справа).
B
2
B
1
R
1
R
2
+
B
2
B
1
R
1
R
2
−
Рис. Исходный набор точек назовем положительным, если для любых двух синих точек B
1
, и любых двух красных точек R
1
, одна из пар отрезков B
1
R
1
, и B
1
R
2
, пересекается во внутренней точке, причем полученный перекресток положителен. Аналогично определяется отрицательный набор.
Пример 4. Пример положительного набора изображен на рис. сравните с задачей Рис. 10 4.1. Раскрасьте точки из примера 1 в два цвета так, чтобы получился отрицательный набор.
В задачах 4.2–4.5 предполагается, что дан некоторый положительный набор, причем N > 2.
4.2. Докажите, что все синие точки лежат по одну сторону от любой прямой, соединяющей две красные точки.
Определение порядка «>». Пусть дан положительный набор.
Пусть и R
2
— две красные точки. Скажем, что R
1
> R
2
, если при движении по прямой от к все синие точки остаются справа

Гл. 14. Комбинаторная геометрия. Докажите, что если R
1
> и R
2
> R
3
, то R
1
> R
3 4.4. Докажите, что если отрезок проходит выше R
2
B
2
, то R
1
>
> R
2 4.5. Докажите, что красные и синие точки можно занумеровать так,
что при любых i < j и k 6= l отрезок R
i
B
k проходит выше Контрольные вопросы. Каково минимальное число точек в раскрашенном в 2 цвета множестве, в которое можно вписать зацепление Хопфа?
а) 6; б) в) где) бесконечно много. Если в положительном наборе изменить цвет каждой точки на противоположный, то набор станет:
а) положительным б) отрицательным;
в) ни положительным, ни отрицательным. Положительный набор при отражении относительно любой вертикальной плоскости станет:
а) положительным б) отрицательным;
в) ни положительным, ни отрицательным. Положительный набор при отражении относительно любой горизонтальной плоскости станет:
а) положительным б) отрицательным;
в) ни положительным, ни отрицательным. При неограниченном движении вертикально вверх наибольшей красной точки (относительно введенного порядка «>») положительного набора а) он все время остается положительным;
б) он через некоторое время становится отрицательным;
в) он через некоторое время становится ни положительным, ни отрицательным. Впишите трилистник в набор точек из примера 4.
4.7. В любой положительный набор 5 синих и 5 красных точек можно вписать трилистник (Теоремы Рамсея). а) Докажите, что для любых m и n найдется такое R(m, n), что при любой раскраске ребер полного графа с R(m, вершинами в два цвета найдется либо полный подграф первого цвета с m вершинами, либо полный подграф второго цвета с n вершинами.
б) Сформулируйте и докажите обобщение пункта а) на случай трех цветов.
в) Сформулируйте и докажите обобщение пунктов аи б) на полные двудольные графы.
г) Назовем набор точек общего положения в пространстве, окрашенных в два цвета, нейтральным, если проекции на плоскость любых

Теория Рамсея для зацеплений
431
двух отрезков с разноцветными концами не пересекаются (во внутренних точках. Докажите, что для любого n найдется такое R(n), что любой набор R(n) синих и R(n) красных точек общего положения в пространстве содержит либо положительный, либо отрицательный, либо нейтральный набор n синих и n красных точек.
д) Докажите, что для любого n найдется такое R(n), что любой набор) синих и R(n) красных точек общего положения в пространстве содержит либо положительный, либо отрицательный набор n синих и n красных точек. Докажите теоремы Ми¨ечи и Негами для трилистника. Впишите узлы и зацепления, изображенные на рис. 3 ив какие-нибудь положительные наборы точек и докажите для них теоремы Ми¨ечи и Негами.
5*. Доказательство теоремы Негами для произвольного зацепления
Лемма (о двух спицах. Пусть в пространстве даны две скрещивающиеся прямые. Для любого узла найдется такое N, что данный узел можно вписать в множество, состоящее из N красных точек на первой прямой и N синих точек на второй прямой.
(Иными словами, любой узел можно натянуть на две спицы.)
Определение (прямоугольного представления узла, рис. 11, слева. Будем говорить, что задано прямоугольное представление узла,
если проекция веревки на плоскость обладает следующими свойствами) проекция состоит из некоторого числа вертикальных и горизонтальных отрезков) никакие два вертикальных отрезка не лежат на одной вертикальной прямой и никакие два горизонтальных отрезка не лежат на одной горизонтальной прямой) если вертикальный и горизонтальный отрезок пересекаются, то горизонтальная часть веревки проходит выше вертикальной.
Определение прямоугольного представления зацепления анало- гично.
Определение (двойственного узла, рис. 11). Пусть дано прямоугольное представление некоторого узла. Пусть x
1
, x
2
, . . . , x
N
— координаты вертикальных, а y
1
, y
2
, . . . , y
M
— координаты горизонтальных отрезков его проекции (рис. 11). Рассмотрим две прямые, параллельные плоскости рисунка, одна из которых расположена под этой плоскостью и проходит горизонтально, а вторая расположена над этой плоскостью и проходит вертикально. Отметим на горизонтальной прямой

Гл. 14. Комбинаторная геометрия точки с координатами x
1
, x
2
, . . . , x
N
, а на вертикальной — точки с координатами. Обозначим через R
i точку на первой прямой с координатой x i
, а через B
j
— точку на второй прямой с координатой y Соединим отрезками все пары отмеченных точек R
i
, B
j
, для которых точка (x i
, y j
) на плоскости рисунка является концом некоторого отрезка проекции узла. В результате получим некоторую замкнутую ломаную. Узел, который представляется этой ломаной, назовем узлом, двойственным к исходному. Определение двойственного зацепления анало- гично.
Пример 5. На рис. 11 изображены трилистники двойственный к нему узел (трилистник).

Контрольные вопросы I. Можно ли назвать картинки де) на рис. 5 прямоугольным представлением узла?
а) Да;

б) нет. Каково минимальное число отрезков в прямоугольном представлении простого зацепления?
а) б) в) г) д) 12.
III. Набор N красных точек R
1
, R
2
, . . . , и M синих точек, B
2
, . . . , из определения двойственного узла является положительным, если и только если:
а) все числа x
1
, x
2
, . . . , x
N
, y
1
, y
2
, . . . , y
M
положительны;
б) все числа x
1
, x
2
, . . . , x
N
, y
1
, y
2
, . . . , y
M
отрицательны;
в) все числа x
1
, x
2
, . . . , x
N
, y
1
, y
2
, . . . , одного знака;
г) числа x
1
, x
2
, . . . , имеют один и тот же знака числа y
1
, y
2
, . . .
. . . , имеют противоположный знак.
x
1
y
1
x
2
y
2
x
3
y
3
x
4
y
4
x
5
y
5
Рис. 11

Теория Рамсея для зацеплений 5.1. Постройте прямоугольные представления узлов и зацеплений с рис. 3 и 4.
5.2. Нарисуйте двойственные узлы и зацепления для построенных вами в задаче 5.1 прямоугольных узлов и зацеплений. Что это за узлы. а) Докажите, что для любого узла существует прямоугольное представление.
б) Докажите, что любой узел можно продеформировать в двойственный к нему. Докажите лемму о двух спицах. Выведите из леммы о двух спицах теоремы Ми¨ечи и Негами.
Дополнительные задачи (очень трудная. Опишите все графы, при любом расположении которых в пространстве найдется пара зацепленных циклов (известная открытая проблема. Опишите все графы, при любом расположении которых в пространстве некоторый цикл оказывается за- узленным.
6*. Доказательство гипотезы Менгера
Этот раздел посвящен одному применению рамсеевской теории зацеплений, а именно доказательству следующего утверждения:
Теорема Уммеля (гипотеза Менгера). Двумерную фигуру, являющуюся произведением двух полных графов на 5 вершинах, нельзя расположить без самопересечений в мерном евклидовом пространстве.
Это утверждение было сформулировано Менгером в 1929 г. в качестве гипотезы, а доказано Уммелем в 1978 г. Мы приведем простое доказательство гипотезы Менгера, полученное одним из авторов статьи.
Для его понимания и для решения некоторых задач данного раздела требуется знакомство с понятием мерного евклидова пространства Однако для того, чтобы увидеть основную идею доказательства, это совсем необязательно. Большинство последующих задач будет относится к случаю плоскости или трехмерного пространства.
Определение (произведения графов. Графом мы называем фигуру, состоящую из точек (вершин, причем некоторые из них соединены отрезками (ребрами, пересекающимися между собой только в вершинах. Соответственно, точка графа — это либо одна из его вершин, либо точка на одном из его ребер.
5)
Мы рассматриваем только достаточно хорошие, то есть кусочно линейные расположения. Мы неприводим их формального определения

Гл. 14. Комбинаторная геометрия
Произведением двух множеств A, B называется множество A × состоящее из всевозможных упорядоченных пар (a; b), где a — точка множества A, а b — точка множества Таким образом, произведение двух графов — это двумерная фигура,
склеенная из квадратиков, отрезков и точек (вершин).
Квадратики соответствуют всевозможным парам (α, β), где α — ребро первого графа, β — ребро второго. Аналогично отрезки соответствуют всевозможным парам (ребро го графа, вершина го графа) и (вершина го графа, ребро го графа, а вершины — всевозможным парам
(вершина го графа, вершина го графа).
Примеры. Произведение двух отрезков — квадрат. Произведение отрезка и окружности — боковая поверхность цилиндра. Произведение двух окружностей — тор. Произведение отрезка на букву Y — книжка стремя страницами. Из скольких квадратиков, отрезков и вершин склеено произведение Обозначим через K
n полный граф на n вершинах, а через K
n,m полный двудольный граф с n синими и m красными вершинами (т. е.
граф, образованный всеми ребрами, соединяющими вершины разных цветов. а) Произведение отрезка на окружность можно расположить на плоскости без самопересечений.
б) Произведение графа на отрезок можно расположить в (трехмерном) пространстве без самопересечений.
в) Произведение графа на окружность можно расположить в (трехмерном) пространстве без самопересечений.
г) Граф можно расположить без самопересечений на двумерном торе.
Проиллюстрируем основную идею разделана следующем примере.
Пример. Докажем от противного, что полный граф на 5 вершинах (граф K
5
) нельзя расположить на плоскости без самопересече- ний. Предположим, что нам удалось это сделать. Пусть O — некоторая вершина этого графа. Рассмотрим на плоскости маленькую окружность с центром O. Она пересекает наш граф в 4 точках. Обозначим данные точки через A, B, C, D в том порядке, в котором они расположены на окружности. Выбросим из нашего графа отрезки, OB, OC, OD — то есть ту его часть, которая попала внутрь рассматриваемой окружности.
В оставшейся части графа пары точек A, C и B, D можно соединить непересекающимися путями. Действительно, пусть A — точка пересече-

Теория Рамсея для зацеплений
435
ния окружности и ребра графа K
5
. Аналогично определим точки, C
′
, D
′
. Тогда пути AA
′
C
′
C и BB
′
D
′
D идут по различным ребрам графа, стало быть, не пересекаются.
Добавим к построенным путям хорды AC и BD нашей окружности. В результате мы получим два замкнутых пути, пересекающихся в единственной точке — точке пересечения хорд AC и Теперь нетрудно прийти к противоречию. Действительно, точки и C находятся по разные стороны от отрезка BD, а следовательно, и по разные стороны от замкнутого пути BDD
′
B
′
B. С другой стороны, эти две точки можно соединить путем AA
′
C
′
C, следовательно, они лежат по одну сторону от замкнутого пути Полученное противоречие показывает, что граф нельзя расположить на плоскости без самопересечений.
6.3. Полный двудольный граф нельзя расположить на плоскости без самопересечений.
Следующая задача посвящена доказательству того, что произведение, где Y — буква ’Y ’, нельзя расположить в трехмерном пространстве без самопересечений.
6.4. Предположим, что произведение Y × Y расположено без само- пересечений в пространстве. Рассмотрим маленькую сферу вокруг точки O × O ⊂ Y × Y , где O — вершина степени 3 графа Y а) Сколько ребер произведения Y × Y выходят из вершин O × б) Сколько квадратиков произведения Y × Y содержат вершину O ×
× в) Как выглядит пересечение данной сферы с произведением Y ×
× Y г) Произведение Y × Y , где Y — буква ’Y ’, нельзя расположить в трехмерном пространстве без самопересечений.
Следующая задача посвящена доказательству того, что произведение графа на окружность нельзя реализовать в (трехмерном) пространстве без самопересечений.
6.5. Предположим, что произведение K
5
× расположено без са- мопересечений в пространстве. Рассмотрим маленькую сферу вокруг точки O
1
× O
2
⊂ K
5
× K
3
, где O
1
, O
2
— вершины графов и K
3
соот- ветственно.
а) Как выглядит пересечение K данной сферы и произведения б) При любом расположении графа K (из пункта а) на сфере в нем найдется цикли пара вершин, расположенных по разные стороны отданного цикла

Гл. 14. Комбинаторная геометрия в) Выведите невозможность расположения K
5
× без самопере- сечений в пространстве из следующего утверждения (доказательства которого мы не требуем число точек пересечения замкнутой двумерной поверхности и замкнутого пути в пространстве, пересекающихся трансверсально, всегда четно. Предположим, что произведение K
5
× расположено без са- мопересечений в R
4
. Рассмотрим маленькую сферу вокруг точки × O ⊂ K
5
× K
5
, где O — вершина графа а) Докажите, что пересечение сферы и произведения K
5
× полный двудольный граф б) (Теорема Закса.) При любом расположении графа в сфере в нем найдется пара циклов с нечетным коэффициентом зацепления.
в) Любую пару циклов в S
3
∩ K
5
× можно заклеить парой непе- ресекающихся двумерных поверхностей, лежащих в произведении K
5
×
× K
5
, но вне шара, ограниченного сферой г) Выведите теорему Уммеля из следующего утверждения (доказательства которого мы не требуем число точек пересечения двух замкнутых двумерных поверхностей в R
4
, пересекающихся трансвер- сально, всегда четно. Как поданному набору графов определить такую минимальную размерность n, что их произведение можно реализовать без самопере- сечений в Ответы на контрольные вопросы
К разделу Зацепленные треугольники I в, II бв, III б.
К разделу Вписанные узлы и зацепления I д.
К разделу Зацепленные четырехзвенные ломаные I б, II бв, III К разделу Доказательство теоремы Негами для трилистника б, II a, III б, IV б, V К разделу Доказательство теоремы Негами для произвольного зацепления б, III в.
Решения задач. Рассмотрим граф, состоящий из шести вершин и всех ребер,
соединяющих их. Каждому человеку сопоставим вершину этого графа. Если двое людей знакомы, то ребро, соединяющее соответствующие им вершины, покрасим в красный цвет, иначе — в синий цвет. Рассмотрим некоторую вершину A. По принципу Дирихле найдутся такие три вершины X
1
, и X
3
, что ребра AX
1
, AX
2
, одного цвета. Для определенности считаем, что это — красный цвет. Если какое-то из ребер) красного цвета, то все стороны треугольника имеют красный цвет, и, тем самым, задача решена. В противном

Теория Рамсея для зацеплений
437
случае все стороны треугольника имеют синий цвет. Ив этом случае задача тоже решена. Первое решение. Если выпуклая оболочка рассматриваемых точек — это четырех- или пятиугольник, то утверждение задачи очевидно пересекутся две диагонали. Рассмотрим случай, когда выпуклой оболочкой является треугольник ABC. Две оставшиеся точки D и E изданных пяти лежат внутри треугольника ABC. Точка E лежит внутри одного из треугольников DAB, DAC или DBC; допустим, в Тогда BE пересекается с одним из отрезков DA или Второе решение. Утверждение этой задачи является двумерным аналогом теоремы 1 и может быть доказано аналогичным образом.
Набор точек на плоскости назовем набором общего положения, если никакие три из них не лежат на одной прямой. Назовем зацепленно- стью пятерки точек общего положения число пар отрезков с концами в этих точках, пересекающихся во внутренней точке. Легко привести пример пятерки, зацепленность которой равна 1. После этого для доказательства утверждения задачи достаточно показать, что четность зацепленности не зависит от выбора 5 точек. Пусть даны две пятерки.
Одну из них можно перевести в другую, по очереди двигая точки (причем движение можно считать равномерным. Пока точки движутся так,
что пятерка остается в общем положении, зацепленность, очевидно, не меняется. Как только одна из точек (скажем, A) попадает на отрезок с концами в двух других точках (скажем, B и C), зацепленность либо не меняется, либо меняется на ±2. Действительно, в такой момент меняется состояние (те. пересекающиеся отрезки становятся непере- секающимися, и наоборот) ровно двух пар отрезков AD, BC и AE, где D и E — две оставшиеся точки пятерки. Достаточно доказать, что если ∆ зацеплен с или зацеплен сто контур треугольника ∆ пересекает плоскость треугольника Первый случай очевиден. Во втором случае контур треугольника пересекает внутренность треугольника ∆. Поэтому внутренность треугольника пересекает плоскость треугольника ∆
′
. Однако в таком случае и контур треугольника ∆ пересекает плоскость треугольника ∆
′
1.4. Указание. Утверждение задачи непосредственно следует из доказанного ниже. Дадим сначала следующее определение.
Определение (зацепленных пар точек. Пусть на горизонтальной прямой отмечено 2 красных и 2 синих точки (точки попарно различны).
Будем говорить, что эти пары зацеплены, если они расположены на прямой в порядке (красная, синяя, красная, синяя) или (синяя, красная,
синяя, красная, считая справа.
Утверждение. Треугольники ∆ и зацеплены ⇔ выполнены следующие условия

Гл. 14. Комбинаторная геометрия) плоскости треугольников ∆ и пересекаются по некоторой прямой l;
2) каждое из множеств ∆ ∩ l и ∆
′
∩ l состоит из двух точек (здесь и далее ∆ и обозначают контуры треугольников) пары точек ∆ ∩ l и ∆
′
∩ l зацеплены на прямой Доказательство. (И, следовательно, решение задачи 1.4). Пусть треугольник ∆ зацеплен с треугольником ∆
′
. Тогда выполнение условия) очевидно. Выполнение условия 2) следует из задачи 1.3. Действительно, так как треугольник ∆ пересекает плоскость треугольника то множество ∆ ∩ l непусто. Из соображений общего положения следует,
что оно не может состоять из одной точки. Докажем теперь выполнение условия 3). Пусть множество ∆ ∩ l состоит из двух точек A и а множество ∆
′
∩ l состоит из двух точек и B
′
. Всеобщие точки контура треугольника ∆ и внутренности треугольника лежат на отрезке. Значит, ровно одна из точек A и B принадлежит отрезку А это означает, что пары A, B и A
′
, зацеплены на Обратно, пусть пары A, B и A
′
, зацеплены на l. Тогда согласно сказанному выше контур треугольника ∆ пересекает внутренность треугольника в единственной точке, то есть ∆ зацеплен с ∆
′
1.5. Из Утверждения, доказанного в решении задачи 1.4, следует,
что треугольники ∆ и зацеплены тогда и только тогда, когда выполняются условия 1)–3) (см. выше. Никакое из этих условий не может нарушиться при допустимом движении. В проверке нуждается лишь сохранение условия 1), которое может нарушиться, только когда плоскости треугольников ∆ и становятся параллельны. Но из задачи следует, что в этот момента также непосредственно дои после него треугольники ∆ и не зацеплены. Решение Д. Коробицына. Пусть треугольники ABC и лежат выше горизонтальной плоскости. Пусть A
′
B
′
C
′
— проекция треугольника на плоскость. Рассмотрим простой многогранник ограниченный многоугольниками ABC, A
′
B
′
C
′
, ABA
′
B
′
, BCB
′
C
′
и
CAC
′
A
′
Треугольники ABC и зацеплены, если и только если число точек пересечения контура треугольника ABC с внутренностью треугольника нечетно. Пусть U — число точек пересечения контура треугольника ABC с боковыми гранями многогранника τ. Число точек пересечения контура с многогранником четно. Поэтому по модулю имеем L + U = 0 ⇒ L = U ⇒ L равно числу точек пересечения контуров проекций треугольников ABC ив которых сторона треугольника проходит ниже стороны треугольника ABC.

Теория Рамсея для зацеплений
439
Утверждение задачи может оказаться полезным при решении других задач из первой части. Указание. Для решения может оказаться полезной следующая лемма.
Лемма. Пусть вершина A треугольника ∆ движется равномерно по отрезку в пространстве, а остальные две вершины и треугольник
∆
′
неподвижны. Обозначим через ∆
t положение треугольника в момент времени t, где 0 6 t 6 2. Предположим, что набор 6 вершин треугольников и находится в общем положении при всех t, кроме t = 1. Тогда:
а) если ∆
1
∩ ∆
′
= ∅, то пары треугольников (∆
0
, ∆
′
) и (∆
2
, зацеплены или не зацеплены одновременно;
б) если и пересекаются в единственной точке, не совпадающей ни с одной из их вершин, то ровно одна из пар треугольников, ∆
′
) и (∆
2
, ∆
′
) зацеплена.
Все интервалы времени, в течение которых рассматриваемые треугольники зацеплены, это 2),
(3, 5; 4, 5),
(6; +Вид этих интервалов следует из примера 3 и леммы, сформулированной выше. Сама лемма легко следует, например, из утверждения, доказанного в решении задачи 1.4.
1.8. Пусть наборы точек N, X
1
, X
2
, X
3
, X
4
, и X
5
, а также N
′
, X
1
,
X
2
, X
3
, X
4
, и находятся в общем положении. Соединим точки и ломаной, не проходящей через отрезки X
i
X
j
. Будем равномерно двигать точку N вдоль этой ломаной, через N
t обозначим ее положение в момент времени t. В соответствии с леммой из указания к задаче зацепленность шестерки точек N , X
1
, X
2
, X
3
, X
4
, может измениться лишь в те моменты времени, когда N
t
∈ X
i
X
j
X
k для некоторых 6 i < j < k 6 5. Поэтому достаточно доказать, что при прохождении точки N через плоскость X
i
X
j
X
k четность зацепленности нашей шестерки не меняется (считаем, что i = 1, j = 2, k = 3). Среди всех возможных отрезков с концами в точках N , X
i
, X
j
, X
k или вообще нет двух пересекающихся отрезков, или имеется только одна пара пересекающихся отрезков. В первом случае контуры любых двух пар треугольников с концами в точках N , X
1
, X
2
, X
3
, X
4
, и не пересекаются;
в соответствии с указанной леммой зацепленность шестерки точек измениться не может. Рассмотрим второй случай. Пусть A
1
, A
2
, A
3
, такая перестановка точек N , X
1
, X
2
, X
3
, что отрезок пересекается с отрезком A
3
A
4
. Существуют две пары треугольников с вершинами в точках N , X
1
, X
2
, X
3
, и X
5
, контуры которых пересекаются

Гл. 14. Комбинаторная геометрия
X
4
A
1
A
2
и X
5
A
3
A
4
, и X
4
A
3
A
4
. Из нашей леммы следует, что коэффициент зацепления каждой из этих пар треугольников поменяется, а коэффициент зацепления остальных пар треугольников останется неизменным. Утверждение задачи доказано. Подходит набор точек из примера 1. Другой пример можно получить, чуть пошевелив набор точек из решения задачи 2.3 а. Утверждение задачи следует из двух предыдущих задач. Указание. Самый правильный способ решить эту задачу — это взять веревку, завязать на ней узел с рис. 5 и попытаться продеформи- ровать его в один из узлов на рис. 3, 4. Тоже относится к зацеплениям.
Деформацию веревки удобно изображать на бумаге в виде серии картинок, в которой соседние картинки получаются друг из друга небольшой деформацией и отличаются мало.
Ответ. а, б) Правый трилистник в) восьмерка г) тривиальный узел д) восьмерка е) зацепление Уайтхеда.
2.2. Достаточно показать, что замкнутая ломаная сне более чем звеньями незаузлена (то есть представляет тривиальный узел. Ясно,
что треугольник незаузлен. Ясно, что если в угольнике (то есть n- звенной замкнутой ломаной) натянутый на пару соседних звеньев треугольник не пересечен никаким другим звеном, то эту пару звеньев можно стянуть по диагонали, то есть получить представление того же узла (n − угольником. Поскольку в угольнике препятствий для стягивания нетто он стягивается в треугольники, значит, незаузлен.
Пусть в угольнике ABCDE есть препятствие для стягивания пары звеньев AB и BC. Тогда звено DE пересекает треугольник ABC. Но тогда звено AE не пересекает треугольник BCD, так как они лежат по разные стороны от плоскости ABC.
2.3. Ответа б) 9; в) 6; г) 7; д) Примеры. Пример к пункту а) изображен на риса. Другой пример правильный треугольник ABC в горизонтальной плоскости, второй треугольник DEF с вершиной F , лежащей вне треугольника в его плоскости, и вершинами D и E, расположенными в точности над и под центром треугольника ABC соответственно.
На рисунках приведены проекции узлов и зацеплений, вписанных в наименьший набор точек. Для каждой проекции нужно еще проверить, что она реализуема, те. действительно существует конфигурация в пространстве, которая проецируется в данную картинку. (О реализуемости таких картинок пространственными ломаными можно почитать в [6], Минимальность. В пунктах аи б) — очевидна. В пункте в) следует из задачи 2.2. Докажем минимальность набора в пункте г. Для это

Теория Рамсея для зацеплений
441
A
1
A
2
A
3
A
4
A
5
A
6
a)
б )
в)
г)
д )
е)
Рис. го достаточно показать, что любая пара треугольников в пространстве либо представляет простое зацепление, либо их можно расцепить. Если контур одного из треугольников не пересекает внутренность другого, то препятствий для расцепления нет. Иначе каждый из контуров треугольников должен пересекать внутренность другого в единственной точке.
Рассмотрим плоскость одного из треугольников (скажем, ABC). Будем считать ее горизонтальной. Пусть сторона DE треугольника пересекает треугольника его третья вершина. Двигая F вертикально
(и вместе с ней — стороны F D и F E), мы можем поместить ее на плоскость. После этого мы можем подвинуть вершины D и E (вместе с соответствующими сторонами) и получить описанный выше пример к пункту а)).
В пунктах д) и е) авторы задачи не умеют доказывать минимальность. Ответа) Да. Следует из примера 3. б) Нет. Первое решение. Допустим, утверждение задачи неверно. Синие точки обозначим C
1
, и C
3
, а красные — K
1
, и K
3
. Тогда стороны четырехугольника не пересекаются во внутренних

Гл. 14. Комбинаторная геометрия точках. Отрезок не пересекается с контуром четырехугольника. Поэтому точки и или обе лежат внутри четырехугольника, или обе вне его.
В первом случае точка лежит внутри одного из четырехугольников или C
1
K
2
C
2
K
3
. Если, например, точка лежит внутри четырехугольника C
1
K
1
C
2
K
3
, то отрезок пересекает контур четырехугольника, что приводит нас к противоречию. Во втором подслучае противоречие получаем аналогичным способом.
Второй случай. Отрезки и не пересекаются с контуром четырехугольника C
1
K
1
C
2
K
2
. Поэтому или точка лежит внутри четырехугольника, или точка лежит внутри четырехугольника. Задача свелась к первому случаю.
Другое решение этой задачи почти дословно повторяет рассуждение из второго решения задачи 1.2.
3.2. Пусть τ — число точек пересечения контура ABCD с гранями тетраэдра A
′
B
′
C
′
D
′
. Тетраэдр делит пространство на две области внутреннюю и внешнюю. Так как точки A, B, C, D, A
′
, B
′
, находятся в общем положении, то число τ четно. Так как ≡ lk(ABCD, A
′
B
′
C
′
D
′
) + lk(ABCD, B
′
C
′
D
′
A
′
)
(mod то lk (ABCD, A
′
B
′
C
′
D
′
) = lk(ABCD, B
′
C
′
D
′
A
′
).
3.3. Определение (коэффициента зацепления двух треугольников. Коэффициентом зацепления двух треугольников ∆ и назовем число lk(∆, ∆
′
) = 1, если ∆ и зацеплены (∆, ∆
′
) = 0, — иначе.
Заметим, что lk(ABCD, A
′
B
′
C
′
D
′
) ≡ lk(ABC, A
′
B
′
C
′
) + lk (ABC, A
′
D
′
C
′
) +
+ lk (ADC, A
′
B
′
C
′
) + lk(ADC, A
′
D
′
C
′
) (mod Из этого, а также из свойств 1.4–1.5 следуют такие утверждения. lk(ABCD, A
′
B
′
C
′
D
′
) = lk(A
′
B
′
C
′
D
′
, ABCD).
2. При непрерывном движении точек A, B, C, D, A
′
, B
′
, C
′
, D
′
, оставляющем их в каждый момент в общем положении, число lk(ABCD,
A
′
B
′
C
′
D
′
) остается постоянным. Пусть даны две замкнутые четырехзвенные ломаные и A
1
B
1
C
1
D
1
, которые не имеют общих точек

Теория Рамсея для зацеплений
443
Первый способ. Пошевелим немного вершины этих ломаных таким образом, чтобы новый набор вершин — A
′
, B
′
, C
′
, D
′
, A
′
1
, B
′
1
, C
′
1
, находился в общем положении. Положим по определению lk(ABCD, A
1
B
1
C
1
D
1
) = lk(A
′
B
′
C
′
D
′
, Второй способ. Пусть α — полуплоскость, ограниченная прямой
A
1
C
1
и содержащая треугольник A
1
B
1
C
1
. А β — полуплоскость, ограниченная прямой и содержащая треугольник A
1
D
1
C
1
. Объединив эти полуплоскости, мы разделим пространство на две части. Каждой точке пересечения контура ABCD с контурами или внутренностями треугольников и поставим в соответствие 0, если существует такая окрестность этой точки, пересечение которой с контуром лежит водной части пространства. В противном случае поставим в соответствие этой точке 1. Коэффициентом зацепления четы- рехзвенных ломаных ABCD и называется сумма всех этих чисел по модулю 2.
3.5. Указанные ломаные будут зацеплены тогда и только тогда, когда пары их вершин на каждой из скрещивающихся прямых будут зацеплены. Поэтому количество зацепленных разделенных пар четырех- звенных ломаных равно 2.
3.6. Пусть даны четыре синие и четыре красные точки, находящиеся в общем положении. Их зацепленностью называется количество зацепленных разделенных пар с вершинами в этих точках.
Пусть B, B
′
, B
1
, B
2
, B
3
— синие точки, а R
1
, R
2
, R
3
, R
4
— красные точки, причем наборы точек B, B
1
, B
2
, B
3
, R
1
, R
2
, R
3
, R
4
, а также B
′
,
B
1
, B
2
, B
3
, R
1
, R
2
, R
3
, находятся в общем положении.
Соединим точки B и ломаной так, чтобы никакое ее звено не лежало нив одной из плоскостей R
i
R
j
B
k
. При движении точки B поло- маной зацепленность набора точек B, B
1
, B
2
, B
3
, R
1
, R
2
, R
3
, может измениться лишь в те моменты, когда отрезок BR
i пересекается с отрезком. Пусть, например, отрезок пересекается с отрезком. Среди всех разделенных пар ломаных с вершинами в нашем наборе точек коэффициент зацепления изменится у следующих и B
1
R
1
B
3
R
4
, и B
1
R
1
B
3
R
3
, и B
1
R
1
B
2
R
4
, и B
1
R
1
B
2
R
3
. Поэтому четность зацепленности при этом не изменится.
Из приведенного рассуждения ясно, что у любых двух наборов из четырех синих и четырех красных точек зацепленность имеет одинаковую четность. Тогда из предыдущей задачи следует, что зацепленность всегда является четной. Для набора общего положения синих точек B
1
, B
2
, B
3
, и красных точек R
1
, R
2
, R
3
, рассмотрим число I таких зацепленных

Гл. 14. Комбинаторная геометрия разделенных пар (, 
′
), что ломаная  содержит отрезок B
1
R
1
. Аналогично рассуждению задачи 3.6 доказывается, что четность числа I не зависит от набора точек. В примере из задачи 3.5 имеем I = 1. Значит,
в каждом наборе число I нечетно, и поэтому в каждом наборе существует зацепленная разделенная пара замкнутых четырехзвенных ломаных. Утверждение задачи следует из задачи. Можно например раскрасить точки A
1
, A
2
, в синий цвета A
4
, A
5
, A
6
— в красный. Непосредственно проверяется, что полученный набор отрицателен. Предположим, что утверждение задачи неверно. Тогда некоторые две синие точки B
1
, расположены по разные стороны от прямой,
проходящей через некоторые две красные точки R
1
, R
2
. Тогда отрезок
B
1
R
1
не пересекает и не пересекает B
2
R
1
, что противоречит определению положительного набора. Пусть, от противного, R
1
> R
2
> R
3
> R
1
. Тогда при обходе треугольника все синие точки все время остаются справа. Это возможно, только если обход происходит почасовой стрелке, и все синие точки расположены внутри треугольника. В задачах 4.2–4.5 предполагается, поэтому есть хотя бы две синие точки. Проведем через них прямую. Какие-то две вершины треугольника расположены по разные стороны от этой прямой. Но тогда исходный набор не может быть положительным (доказывается аналогично задаче 4.2).
4.4. Так как исходный набор точек положителен, то по определению пересечение и положительно. Значит, при движении от к точка остается слева. Но тогда и при движении от к точка остается справа. Значит, по определению R
1
> R
2 4.5. Из задачи 4.3 следует, что красные точки можно занумеровать так, чтобы R
2
< . . . < Из задачи 4.4 следует, что эта нумерация — искомая (решение В. Челнокова). Занумеруем красные и синие точки слева направо. Тогда трилистник представляется ломаной 4.7. Пусть дан положительный набор 5 красных и 5 синих точек.
Занумеруем красные точки, как в задаче 4.5. Занумеруем синие точки аналогичным образом. А именно, можно определить порядок «>» синих точек аналогично порядку красных точек и занумеровать синие точки в порядке возрастания (в смысле «>»). Рассмотрим ломаную
R
1
B
4
R
4
B
1
R
2
B
3
R
5
B
5
R
3
B
2
R
1
(см. решение задачи 4.6). Она представляет трилистник, что вытекает из следующей леммы

Теория Рамсея для зацеплений
445
Лемма. Положительный набор 5 синих и 5 красных точек можно перевести в набор точек из примера 6 непрерывным движением так,
чтобы в процессе движения набор оставался в общем положении.
Идея доказательства. Рассмотрим точку B
1
. Из нашей нумерации точек следует, что отрезки с началом расположены выше всех остальных. Поэтому мы можем переместить (допустимым образом) точку так, чтобы ее проекция попала в самую левую синюю точку на риса сама точка располагалась очень высоко над плоскостью рисунка. Тогда и все отрезки с началом будут располагаться очень высоко. Тоже самое можно сделать и сточкой так расположить ее очень высоко, но ниже точки B
2
, чтобы ее проекция совпала со второй слева синей точкой. Действуя таким образом со всеми синими точками,
а потоми с красными, мы переведем исходный набор точек в требуемый набор. Лемма, а вместе с ней и утверждение задачи 4.7, доказана. (Небольшой экскурс в рамсеевскую теорию графов.)
а) Утверждение легко доказать индукцией по n + m. Докажем базу + m = 6). Всюду в дальнейшем через R(m, n) будем обозначать минимальное число вершин в полном графе с требуемым свойством. Из задачи 1.1 следует, что R(3, 3) = 6. Очевидно, R(4, 2) = 4. База доказана. Индукционный переход в случае n = 2 или m = 2 очевиден. При m, n > 2 индукционный переход получается из оценки, m) 6 R(n − 1, m) + R(n, m − Действительно, рассмотрим полный граф с R(n − 1, m) + R(n, m − вершинами. Рассмотрим его вершину A. По принципу Дирихле найдется либо R(n − 1, m) выходящих из нее ребер первого цвета, либо, m − 1) выходящих из нее ребер второго цвета. Рассматривая полные подграфы с вершинами в отличных от A концах указанных ребер,
получаем требуемое. Утверждение доказано.
б) Формулировка очевидна, доказательство аналогично пункту аи использует оценку, m, n) 6 R(l − 1, m, n) + R(l, m − 1, n) + R(l, m, n − 1).
в)
Теорема. Для любых m
1
, m
2
, m
3
, n
1
, n
2
, найдется такое = R(m
1
, m
2
, m
3
, n
1
, n
2
, что при любой раскраске в три цвета двудольного графа с 2R вершинами (поровну в каждой доле) для некоторого 1 6 i 6 3 найдется полный двудольный подграф го цвета с m вершинами впервой доле и n вершинами во второй

Гл. 14. Комбинаторная геометрия
Доказательство аналогично пункту аи использует оценку 6 R(m
1
− 1, m
2
, m
3
, n
1
, n
2
, n
3
) + R(m
1
, m
2
− 1, m
3
, n
1
, n
2
, n
3
) +
+ R(m
1
, m
2
, m
3
− 1, n
1
, n
2
, г) (Идея доказательства) Сначала нужно доказать следующее вспомогательное
Утверждение. Пусть дан полный двудольный граф сверши- нами (поровну в каждой доле. Назовем треугольником три вершины,
одна из которых лежит впервой доле, а две другие — во второй. Тогда для любых n
1
, n
2
, и m
1
, m
2
, найдется такое = R(m
1
, m
2
, m
3
, n
1
, n
2
, что при любой раскраске всех треугольников в три цвета найдется полный двудольный подграф с m вершинами впервой доле и n вершинами во второй, все треугольники которого имеют цвет Доказательство производится индукцией по i
+
P
m i
. База индукции состоит в утверждениях задач 4.7 б) ив. Индукционный переход получается из оценки 6 R R(m
1
− 1, m
2
, m
3
, n
1
, n
2
, n
3
), R(m
1
, m
2
− 1, m
3
, n
1
, n
2
, n
3
),
R(m
1
, m
2
, m
3
− 1, n
1
, n
2
, Здесь R(x, y, z) — число из пункта 4.7 б. Для доказательства приведенной формулы нужно рассмотреть одну из вершин впервой доле, скажем. Без ограничения общности, согласно пункту 4.7 б) можно отметить) вершин во второй доле так, чтобы все треугольники с вершинами в A и двух отмеченных точках были первого цвета. Теперь наша формула получается из предположения индукции.
Для доказательства утверждения 4.7 г) нужно рассмотреть одну синюю вершину B
1
. Каждую тройку B
2
, R
1
, раскрасим в один из трех цветов в зависимости оттого, положительна, отрицательна или нейтральна четверка B
1
, B
2
, R
1
, R
2
. Теперь проходит индукционный переход, использующий предыдущее утверждение и аналогичный доказательству этого утверждения. Тем самым утверждение задачи 4.7 г)
может быть доказано по индукции.
д) Согласно задаче 3.1, нейтральных наборов при n > 3 не бывает.
Поэтому пункт д) следует из пункта г. Теоремы Ми¨ечи и Негами для трилистника следуют из задачи, ее аналога для отрицательного набора и задачи 4.8 д) для n = 5.

Треугольники и катастрофы 4.10. Лучший способ решить эту задачу — воспользоваться задачами и 5.2 из раздела Доказательство теоремы Негами». Как ив решении задачи 2.1, для проверки лучше всего использовать веревку или нить.
Литература
[1] Conway J., Gordon C. Knots and links in spatial graphs // J. of Graph
Theory. 1983. Vol. 7. P. 445–453.
[2] Negami S. Ramsey-type theorem for spatial graphs // Graphs and Com- binatorics. 1998. Vol. 14. P. 75–80.
[3] Skopenkov M. Embedding products of graphs into Euclidean spaces //
Fundamenta Mathematicae. 2003. Vol. 179. P. 191–197.
http://arxiv.org/abs/0808.1199
[4] Прасолов В, Скопенков М. Рамсеевская теория зацеплений // Математическое просвещение. Третья серия. 2005. Т. 9. С. 108–115.
[5] Скопенков М, Скрябин О, Шаповалов А. Вписанные зацепления Материалы XV Летней конференции международного математического Турнира городов Богданов И, Каибханов А, Кудряшов Ю, Скопенков А, Сосин- ский А, Челноков Г. Новые способы плетения корзин // Материалы Летней конференции международного математического Турнира городов Гайфуллин А, Скопенков А, Скопенков М, Шаповалов А. Проекции скрещивающихся прямых. Материалы XIII Летней конференции международного математического Турнира городов,
http://www.turgor.ru/lktg/2001/index.php
Треугольники и катастрофы
6)
(10–11)
А. Я. Канель-Белов, А. К. Ковальджи
В Кванте № 2 за 1992 г. была опубликована задача На плоскости проведено n прямых общего положения (никакие три не проходят через одну точку и никакие две не параллельны. Докажите, что среди частей, на которые они делят плоскость, не меньше а) n/3; б) (n − 1)/2; в n − 2 треугольников.
6)
Данный материал представляет собой переработанный вариант статьи в журнале Квант, 1992, № 11.

Гл. 14. Комбинаторная геометрия
Нас будет интересовать точная оценка числа треугольников. Эта задача, простая и увлекательная по формулировке, была поставлена еще в 1870 году и стала проблемой на сто с лишним лет. Она затягивает,
и кажется, — решение вот-вот получится. Но много лет каждая Эврика лишь пополняла нашу коллекцию тонких ошибок.
Первое решение получили в 1979 г. известные геометры Грюнбаум и Шеппард. Здесь мы излагаем более короткое элементарное решение,
найденное А. Я. Канелем-Беловым. По существу его можно записать на половине страницы, однако формальный текст мало что даст для понимания. Поэтому мы проследим путь, на котором получено решение,
и выявим ключевые идеи на интуитивном уровне.
Ослабленная формулировка
На Московской математической олимпиаде в 1972 году была предложена следующая задача.
Задача 1. На плоскости проведено 3000 прямых, причем никакие две из них не параллельны и никакие три не пересекаются водной точке. По этим прямым плоскость разрезали на куски. Докажите, что среди кусков найдется не менее а) 1000 треугольников, б) 2000 треугольников.
Решение. Пункта) совпадает с пунктом а) задачи M1330, при n =
= 3000, а пункт б) является усилением ее пункта б, поскольку 2000 >
> (3000 − Начнем с ключевой идеи. К каждой прямой примыкает хотя бы один треугольник (треугольный кусок с основанием на прямой. Если это доказать, то получится решение пункта а, поскольку каждый треугольник примыкает к трем прямым.
Попробуем найти для каждой прямой примыкающий к ней треугольник, не пересеченный другими прямыми. Здесь красивая идея выберем ближайшую к этой прямой точку пересечения других прямых (рис. Покажите, что эта точка — вершина искомого треугольника.
Рис. 1. Ближайшая точка пересечения

Треугольники и катастрофы
449
Чтобы доказать пункт б, достаточно для каждой прямой найти еще один примыкающий к ней треугольник. Это кажется просто ведь упрямой две стороны. Беда лишь в том, что все точки пересечения могут лежать по одну сторону от прямой. Ноне является ли этот плохой случай редкостью Давайте посмотрим, сколько плохих прямых может быть.
Очевидно, возможен случай, когда плохих прямых ровно три (когда прямых всего три. К счастью, это самый плохой случай (больше не бывает. Если же прямых n > 3, то плохих прямых не больше двух.
Докажем это.
Допустим, что есть тройка плохих прямых. Нарисуем только их и еще одну прямую. В любом случае появятся точки пересечения по обе стороны от одной из плохих прямых (поскольку на четвертой прямой лежат три точки пересечения, а прямая, проходящая через среднюю точку, не может быть плохой. Противоречие.
Итак, при n > 3 найдется не больше двух прямых, к которым примыкает ровно один треугольника к остальным примыкает не меньше двух. Оценим число треугольников. Их будет не меньше (2n − В нашем случае это 1999 и 1/3. Но число треугольников целое, значит,
их не меньше Попутно доказано усиление пункта б) задачи M1330, поскольку − 1)/3 > (n − Предлагаем вам несколько упражнений, идейно близких к только что решенной задаче.
Упражнения
1. В пространстве провели n плоскостей общего положения (любые четыре образуют тетраэдр. Докажите, что среди частей разбиения пространства найдется не меньше а) n/4 тетраэдров (n > 4), б) (2n − 3)/4 тетраэдров (n > 5).
2. На плоскости отмечено n прямых (n > 3). Любые две из них пересекаются, и через каждую точку пересечения проходит не меньше трех прямых. Докажите, что все прямые пересекаются водной точке. В пространстве отмечено n плоскостей. Любые три из них имеют общую точку, и через каждую такую точку проходит не меньше четырех плоскостей. Докажите, что все плоскости проходят через одну точку. (На идею ближайшей прямой) На плоскости отмечено n точек.
Через каждые две из них проведена прямая. На каждой такой прямой лежит не менее трех отмеченных точек. Докажите, что все отмеченные точки лежат на одной прямой

Гл. 14. Комбинаторная геометрия
Точная оценка — тонкие ошибки
Теперь приступим к нашей главной задаче.
На плоскости провели n прямых общего положения (любые три образуют треугольник. Докажите, что среди частей разбиения плоскости найдется по крайней мере n − 2 треугольника, причем эта оценка точная. Расположите n прямых общего положения так, чтобы треугольных кусков было ровно n − 2. (Указание. Проведите несколько касательных к дуге окружности.)
В основе всех первоначальных попыток доказательства точной оценки лежало наблюдение, что треугольник «неуничтожим», те. секущая прямая делит его на две части, одна из которых — треугольник. (Кстати, верно ли аналогичное утверждение для тетраэдра и секущей плоскости. 2. От каждого треугольника с основанием на AB остался треугольник
Вот одно из красивых ошибочных решений.
Если найти любые n − 2 треугольника, то после их пересечения прямыми от них останется n − 2 треугольных кусочка, и задача будет решена. Для этого выделим одну прямую AB. Остальные прямые пересекают ее в n − 1 точке. Эти точки делят прямую на n − 2 отрезка. Прямые,
проходящие через концы отрезков, образуют сними треугольника
(рис. 2). Эти треугольники неуничтожимы. Вот и все. Найдите ошибку в этом решении. (Указание. Вершина одного треугольника попадает внутрь другого треугольника.)
Попытка применить индукцию
Поскольку треугольник неуничтожим, естественно попытаться применить индукцию например, доказать, что добавление прямой увеличит число треугольников. Именно на этом пути получено большинство

Треугольники и катастрофы
451
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
Рис. 3. Удаление прямой AB не уменьшает число треугольников ошибочных решений. А дело в том, что это утверждение неверно добавление прямой может не прибавить треугольников!
Нарисуем несколько прямых общего положения так, чтобы при удалении прямой AB число треугольников не уменьшилось (рис. Были попытки доказать, что всегда найдется прямая, удаление которой уменьшит число треугольников (тогда бы прошла индукция. Но вопрос остался открытым верно ли, что такая прямая найдется Решение было получено из других соображений.
Итак, добавление и удаление прямых нам не помогло, поищем другой путь.
Избегать крайностей — тоже крайность
В понятии общего положения прямых заметно стремление уйти от вырожденных случаев. Уже само слово вырожденный создает ощущение патологии, чего-то такого, чего надо избегать. И школа приучает к этому, запрещая, например, три точки, лежащие на одной прямой,
считать треугольником. Однако именно идея вырождения (упрощения)
оказалась краеугольным камнем решения задачи о треугольниках. Начнем с примера.
Задача 2. В выпуклом пятиугольнике каждая диагональ отсекает треугольник. Докажите, что сумма площадей этих треугольников больше площади пятиугольника.
Решение. Иметь дело с произвольным пятиугольником довольно трудно. А нельзя ли его упростить Ноне ради разбора частного случая (хотя и это полезно, а для того чтобы свести общий случай к частному.
Давайте двигать вершину A пятиугольника параллельно его диагонали основанию треугольника (риса. Тогда площадь треугольника и площадь пятиугольника не будут меняться, но будут меняться площади треугольников ABC и ADE.

Гл. 14. Комбинаторная геометрия
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
а
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
б
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
б
Рис. 4. Вырождение (упрощение) пятиугольника. Закрашены треугольники,
площадь которых меняется
Ключевая идея если двигать вершину треугольника вдоль прямой
(сохраняя основание, то его площадь будет либо возрастать, либо убывать, либо не меняться (высота либо растет, либо убывает, либо не меняется. Иными словами если двигать вершину вдоль прямой с постоянной скоростью, то площадь треугольника тоже меняется с постоянной скоростью. Значит, сумма площадей всех треугольников тоже меняется с постоянной скоростью. Хорошо, если она не растет, потому что мы надеемся доказать неравенство для нового пятиугольника так, чтобы для старого оно было верно и подавно.
Но если суммарная площадь треугольников растет, что тогда делать Очень просто надо двигать вершину в противоположную сторону, и площадь будет убывать.
До каких же пор двигать вершину Очевидно, пока пятиугольник остается выпуклым. Нов этом предельном положении (рис. 4 б ) один из углов пятиугольника равен 180 градусов. Ну и пусть, ведь пятиугольник стал проще (Стал похож на четырехугольник.)
Теперь повторим это рассуждение для вершины E с развернутым углом. Что получится Она совпадет с одной из соседних вершин, например с D (рис. 4 в).
Можно двигать вершины и дальше, до предела, когда пятиугольник превратится в треугольник (с двумя двойными вершинами или одной тройной, но можно остановиться и раньше, поскольку треугольники и BCD уже покрывают пятиугольник.
Итак, доказательство для исходного пятиугольника свелось к одному частному (вырожденному) случаю, который очевиден. Точнее, мы сохраняли площадь пятиугольника, меняя его форму так, чтобы суммарная площадь треугольников убывала. В результате треугольники покрыли пятиугольник, значит, их площадь была больше

Треугольники и катастрофы
453
Замечание. Можно двигать вершины пятиугольника вдоль произвольной прямой, тогда все площади будут меняться линейно (с постоянной скоростью, и нам достаточно следить затем, чтобы разность площадей треугольников и пятиугольника (которая тоже меняется линейно) убывала.
Такими же средствами решается и ряд других задач.
Упражнения
7. В выпуклом шестиугольнике каждые три соседние вершины образуют треугольник. Всегда ли сумма площадей этих треугольников больше площади шестиугольника. Из бумажного параллелограмма вырезали треугольник. Докажите, что площадь треугольника не превосходит половины площади параллелограмма. Докажите, что у выпуклого многоугольника найдутся три вершины, которые образуют треугольник максимальной площади среди треугольников, вписанных в него. В кубе сидит выпуклое тело, чья проекция на любую грань куба полностью ее покрывает. Докажите, что объем тела не меньше трети объема куба. На отрезке отмечено n точек. Какова максимально возможная сумма попарных расстояний между ними. Покажите, что максимум линейной функции от координат точек внутри выпуклого многогранника достигается водной из его вершин. Али-Баба пришел в пещеру, где есть золото, алмазы и сундук.
Полный сундук золота весит 200 кг, а полный алмазов – 40 кг. Пустой сундук ничего не весит. Килограмм золота стоит 20 динариев, а килограмм алмазов — 60. Сколько денег может выручить Али-Баба за сокровища, если он может унести не больше 100 кг (Указание. 1 г алмазов дороже 1 г золота, но 1 мл алмазов дешевле 1 мл золота. Докажите, что сундук должен быть полон и при этом весить 100 кг.)
Во всех этих задачах хорошо работают три идеи 1) сведение общей ситуации к частному случаю посредством движения, 2) выбор линейного движения, которое водном из направлений улучшает ситуацию) рассмотрение граничных (краеугольных) случаев, которые часто бывают вырожденными.
Сама возможность не вникать в процесс движения, а сразу смотреть во главу угла принципиально важна мы встретим ситуацию, когда ва-

Гл. 14. Комбинаторная геометрия рианты движения необозримы, но можно воспользоваться информацией о финальном состоянии.
Поэтому в дальнейшем мы будем 1) двигать прямые, приводя их расположение к удобному виду, 2) использовать линейное движение, т. е.
параллельный перенос с постоянной скоростью, 3) изучать предельные положения прямых.
План действий
Ближайшие рассуждения не войдут в окончательное решение, однако их стоит рассмотреть, поскольку, во-первых, они привели к решению,
во-вторых, похожими средствами решаются многие трудные задачи,
и в-третьих, полезно проследить чистку решения. В результате мы получим решение на интуитивном уровне. Затем сделаем рассуждения строгими и, наконец, приведем короткое формальное доказательство.