Текст статьи Бекламов Б. В. Применение теоремы Эйлера к некоторым задачам // Квант. — 1974. — № 10. — С. 17—19.
В этой статье мы предлагаем читателям несколько задач, в решении которых центральную роль играет теорема Эйлера. Уделяя основное внимание задачам, мы не доказываем здесь эту теорему, а приводим лишь её формулировку. Доказательство теоремы Эйлера, как и более общие формулировки этой теоремы, можно найти в книгах «Что такое математика?» Куранта и Роббинса и «Наглядная геометрия» Гильберта и Кон-Фоссена.
Прежде чем формулировать теорему Эйлера, договоримся, что линию с концами в двух данных точках мы будем называть дугой, соединяющей эти точки, в том случае, если эту линию можно пройти, не побывав ни в одной из её точек дважды.
Теорема Эйлера. Пусть на плоскости задано
В случае, изображённом на рисунке 1, все условия теоремы Эйлера выполнены,
В некоторых задачах совокупность, состоящую из нескольких точек и соединяющих их попарно непересекающихся дуг, мы называем картой; при этом точки из этой совокупности мы называем вершинами, а области, на которые дуги делят плоскость, — странами.
Теперь мы можем перейти к решению задач.
Задача 1. Можно ли десять городов соединить между собой непересекающимися дорогами так, чтобы из каждого города выходило пять дорог, ведущих в пять других городов?
Решение. Предположим, что города можно соединить между собой дорогами так, как сказано в задаче. В таком случае, если какие-то два города окажутся не соединёнными дорогой непосредственно, то найдётся третий город, который уже будет непосредственно соединён с каждым из них. Изобразив на плоскости города точками, а дороги — дугами, получим, что любые две точки соединены цепочкой дуг. Так как в каждой точке сходится пять дуг, то общее число дуг равно
Задача 2. Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Решение. Предположим, что это сделать можно.
Изобразим дома синими, а колодцы чёрными точками и каждую синюю точку соединим дугой с каждой чёрной точкой так, чтобы девять полученных дуг попарно не пересекались. Тогда всякие две точки, изображающие дома или колодцы, будут соединены цепочкой дуг, и в силу теоремы Эйлера девять дуг разделят плоскость на
Задача 3. Докажите, что на всякой карте найдётся страна, граничащая не более чем с пятью странами.
Решение. Если число стран на карте не превосходит шести, то утверждение задачи очевидно. Мы докажем, что на карте, имеющей более шести стран, найдутся даже четыре страны, каждая из которых граничит не более чем с пятью странами. Украсим вершины и дуги исходной карты в чёрный цвет, а красной краской отметим в каждой стране по одной точке. Всякие две отмеченные точки, лежащие в соседних странах (т. е. странах, имеющих общую граничную дугу), соединим внутри этих стран красной дугой так, чтобы красные дуги попарно не пересекались. Тогда всякие две красные точки будут соединены цепочкой дуг, и так как никакие две односторонние дуги не будут соединять одни и те же точки, то каждая страна на карте, состоящей из точек и дуг красного цвета, будет ограничена не менее чем тремя дугами. Если какая-то страна на этой карте ограничена более чем тремя дугами, то на её границе можно выбрать две вершины, не соединённые дугой, и соединить их красной дугой внутри этой страны. Повторяя несколько раз эту операцию, мы получим красную карту, на которой каждая страна ограничена ровно тремя дугами. Так как, кроме того, на этой карте никакие две дуги не соединяют одни и те же вершины и так как число вершин больше трёх, то из каждой вершины выходят не менее чем три дуги. Обозначим через
Из формулы (1) и теоремы Эйлера, применённой к системе точек и дуг красного цвета, следует, что $$
\begin{gather*}
2n=6m-12,\\
3a+6(m-a)\le6m-12,
\end{gather*}
$$
которое показывает, что
Задача 4. Можно ли семиугольник разрезать на выпуклые шестиугольники?
Решение. Предположим, что какой-то семиугольник удалось разрезать на выпуклые шестиугольники. Обозначим число тех вершин шестиугольников, которые лежат внутри исходного семиугольника, через
Так как внешняя область ограничена
Из некоторых вершин на границе семиугольника выходит только две дуги. Обозначим число таких вершин через
Так как на границе семиугольника найдутся по крайней мере две вершины, из которых выходят дуги, ведущие внутрь семиугольника, то
С другой стороны, так как семиугольник разрезан на выпуклые многоугольники, то всякая вершина, из которой выходят две дуги, является вершиной семиугольника, и потому
Следующие задачи мы предлагаем читателю решить самостоятельно.
Упражнения
- Можно ли пять городов соединить между собой непересекающимися дорогами так, чтобы из каждого города в любой другой город вела дорога, не проходящая через остальные города?
- Докажите, что если на карте число стран больше девятнадцати, то на этой карте найдутся три страны с одинаковым числом соседей.
- Пятиугольник разрезан на несколько многоугольников так, что все стороны исходного пятиугольника остались неразрезанными. Докажите, что если число получившихся многоугольников не менее пяти, то в одном из них найдётся угол, который больше либо равен
$72^\circ$. - Треугольник, все углы которого не больше
$120^\circ$, разрезан на несколько треугольников. Докажите, что в одном из получившихся треугольников все углы не больше$120^\circ$. - В игре принимают участие два игрока. Перед началом игры на плоскости отмечается
$m$ точек. Игроки поочерёдно разыгрывают две точки, ещё не соединённые дугой, и соединяют эти точки дугой, которая не пересекает ранее построенные дуги. Выигрывает тот, кто делает последний ход. При каких$m$ выигрывает игрок, делающий первый ход, а при каких — его противник?