Задача 73610

Темы:    [ Обходы многогранников ] [ Параллельное проектирование (прочее) ] [ Выпуклые тела ] [ Индукция в геометрии ] [ Процессы и операции ]

Сложность: 6+ Классы: 10,11

Условие

Автор: Кушниренко А.Г.

а) Сумма длин рёбер любого выпуклого многогранника больше утроенного диаметра. Докажите это. (Диаметром многогранника называют наибольшую из длин всевозможных отрезков с концами в вершинах многогранника.)

б) Для любых двух вершин A и B любого выпуклого многогранника существуют три ломаные, каждая из которых идёт по рёбрам многогранника из А в В и никакие две не проходят по одному ребру. Докажите это.

в) Если в выпуклом многограннике разрезать два ребра, то для любых двух его вершин А и В существует соединяющая эти две вершины ломаная, идущая по оставшимся рёбрам. Докажите это.

г) Докажите, что в задаче б) можно выбрать три ломаные, никакие две из которых не имеют общих вершин, за исключением точек А и В.

Решение

Очевидно, что из задачи г) следует задача б), из б) следуетв) и а). Заметим еще, что с помощью теоремы Форда-Фалкерсона о максимальном потоке и минимальном разрезе (см. "Квант" #4, 1970г., стр.24, задача 4) легко из в) вывести б); достаточно применить эту теорему к сети, образуемой ребрами многогранника (каждое ребро считается дважды – "туда" и "обратно"). Мы приведем набросок коротких доказательств а) и в) и решим г).

а) Пусть AB – диаметр M . Спроектируем все ребра M на AB.
Посмотрим, сколько точек проектируется в какую-нибудь точку C , лежащую внутри AB . Если через C провести плоскость P перпендикулярно AB, то P пересечет AB по выпуклому многоугольнику. Вершины этого многоугольника (а их не меньше трех!) суть точки пересечения P с ребрами M и, значит, в каждую внутреннюю точку отрезка AB проектируется не менее трех ребер M . Отсюда легко вывести утверждение задачи а).

При решении задач в) и г) мы будем использовать следующее интуитивно очевидное утверждение: для любых двух вершин A и B выпуклого многогранника M существует путь из A в B по ребрам M. Доказательство мы оставляем читателю.

в) Пусть разрезаны ребра r₁ и r₂ . Очевидно, что существует путь L₁, соединяющий концы r₁ и не проходящий через r₂.
Действительно, к ребру r₁ прилегают две грани. Ребро r₂ не лежит хотя бы на одной из этих граней, поэтому за L₁ можно взять путь по ее границе. Аналогично, для ребра r₂ существует путь L₂.
Рассмотрим теперь две произвольные вершины A и B. Как было сказано выше, существует путь L, идущий из A в B по ребрам M. Заменив в пути L ребро r₁ на путь L₁, а ребро r₂ на путь L₂ (если, конечно, эти ребра встречаются в L), мы получим искомый путь по оставшимся ребрам. Заметим, что этот путь может иметь самопересечения, которые, впрочем, нетрудно устранить.

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

Для доказательства утверждения задачи мы фиксируем точку A и будем проводить индукцию по расстоянию между точками A и B.
Если d(A,B) = 1, то A и B лежат на одном ребре, и утверждение очевидно, так как можно пройти из A в B по ребру AB и границам двух граней, прилегающих к AB .
Предположим, что утверждение доказано для всех вершин, лежащих от A на расстоянии n - 1 . Пусть d(A,B)=n . Тогда существует вершина B' такая, что d(A,B) = n - 1 и d(B',B) = 1. Рассмотрим все грани, содержащие B' . Множество всех ребер, принадлежащих всем таким граням, состоит из "радиусов" (ребер с концом B' ) и "кольца" (которое образуют остальные ребра). Одной из вершин кольца является точка B. По предположению индукции существуют три пути l₁ , l₂ , l₃ из A в B' , не имеющие попарно общих точек, кроме концов. Очевидно, что каждый из этих трех путей проходит хотя бы через одну вершину кольца. Такие вершины кольца назовем занятыми.
Будем теперь двигаться из точки B по кольцу в одном направлении, пока не попадем в первую занятую вершину, а затем в другом направлении. Рассмотрим две полученные занятые вершины A₁ и A₂ (одна из них может быть вершиной B ). Возможны два случая.

Случай 1. Занятые вершины A₁ и A₂ принадлежат разным путям, скажем l₁ и l₂ . Тогда мы строим три пути из A в B следующим образом.
          Первый путь: из A в A₁ по l₁ , затем из A₁ в B по кольцу (заметим, что по построению точки A₁ на последнем участке мы не пересекаемся с путями l₂ и l₃ ).
          Второй путь: из A в A₂ по l₂ , затем из A₂ в B по кольцу.
          Третий путь: из A в B' по l₃ , затем по ребру B'B .
Очевидно, что построенные три пути попарно не имеют общих точек, кроме концов.

Случай 2. Занятые вершины A₁ и A₂ принадлежат одному пути, скажем l₁ . Посмотрим тогда, какая на этих вершин встречается раньше при движении от A к B' по l₁ и возьмем отрезок l'₁ пути l₁ от A до первой из этих вершин. После этого рассмотрим три пути l'₁ , l₂ , l₃ , рассмотрим множество вершин кольца, занятых путями l'₁ , l₂ , l₃ и проведем снова предыдущие рассуждения применительно к этим трем путям.
Если нам встретится случай 1, то мы построим искомые пути описанным выше способом, если же снова встретится случай 2, то мы рассмотрим новую тройку путей l''₁ , l₂ , l₃ . Если и для этой тройки возникнет случай 2, то мы рассмотрим новую тройку и т.д. Поскольку мы при этом отходим по кольцу все дальше и на кольце есть вершины, принадлежащие путям l₂ и l₃ , то на некотором шаге мы получим случай 1 и искомые пути из A в B будут построены.
Задача г) решена.

Верно еще более сильное утверждение: для любых двух вершин A и B можно найти три цепочки граней, не имеющие общих граней и в каждой из которых первая грань содержит вершину A , последняя – вершину B и соседние грани имеют общее ребро.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1971
выпуск
Номер	3
Задача
Номер	М75