ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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. Доказательство мы оставляем читателю.

в) Пусть разрезаны ребра r1 и r2 . Очевидно, что существует путь L1, соединяющий концы r1 и не проходящий через r2.
Действительно, к ребру r1 прилегают две грани. Ребро r2 не лежит хотя бы на одной из этих граней, поэтому за L1 можно взять путь по ее границе. Аналогично, для ребра r2 существует путь L2.
Рассмотрим теперь две произвольные вершины A и B. Как было сказано выше, существует путь L, идущий из A в B по ребрам M. Заменив в пути L ребро r1 на путь L1, а ребро r2 на путь L2 (если, конечно, эти ребра встречаются в 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. По предположению индукции существуют три пути l1 , l2 , l3 из A в B' , не имеющие попарно общих точек, кроме концов. Очевидно, что каждый из этих трех путей проходит хотя бы через одну вершину кольца. Такие вершины кольца назовем занятыми.
Будем теперь двигаться из точки B по кольцу в одном направлении, пока не попадем в первую занятую вершину, а затем в другом направлении. Рассмотрим две полученные занятые вершины A1 и A2 (одна из них может быть вершиной B ). Возможны два случая.

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

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

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .