Короче, Склифосовский!

Ответы на оба вопроса положительны.

В задаче а) кажется естественным провести дорожки по диагоналям квадрата, но это даёт длину 200√2 ≈ 2828 м — а на самом деле можно провести дорожки короче.

В задаче б) «стандартная» развёртка имеет периметр 60 см (рис. 1), при этом три вершины треугольника «склеиваются» в одну вершину тетраэдра (попробуйте себе мысленно представить, как это происходит).

Рис. 1.

Если же клеить тетраэдр по ломаной линии, проходящей через две вершины и середину противоположного ребра (красная линия на рис. 2), то развёртка окажется прямоугольником, две стороны которого равны ребру (проверьте!), а две других — удвоенной длине отрезка, соединяющего вершину с серединой противоположной стороны.

Рис. 2.

В правильном треугольнике со стороной 10 см каждый такой отрезок равен 5√3 ≈ 8,66 см. Таким образом, периметр такой развёртки оказывается равным 20 + 20√3 ≈ 54,64 см. Это, конечно, лучше, чем 60, но тоже не предел.

Рис. 3.

Попробуйте сложить тетраэдр из шеститиугольной развёртки, показанной на рис. 3. Когда у вас это получится, подумайте, как сосчитать длину периметра для такой развёртки.

Этот рассказ мы с загадки начнём,
Даже Алиса ответит едва ли:
Что остаётся от сказки потом,
После того, как её рассказали?
В. Высоцкий

а) А мы начнём с опровержения задачи. Вернее, с софизма — попытаемся доказать, что улучшить значение 2000√2 нельзя.

Пусть A, B, C, D — четыре вершины квадрата и мы как-то провели соединяющие их дорожки. Если мы при этом не отступали от сторон квадрата, то для соединения четырех вершин мы должны полностью провести три стороны, а это даёт длину дорожек 3000 м. А поскольку это больше, чем 2000√2, то такой вариант не является минимальным.

Следовательно, мы провели какие-то дорожки внутри квадрата, а значит, то множество дорожек, которое позволяет совершить прогулку от A к C, пересекается с множеством, которое позволяет прогуляться от B к D (рис. 4).

Рис. 4.

Красным цветом изображена точка пересечения I. От нее по четырем разным направлениям можно добраться до четырех вершин квадрата. Но каждый такой путь не короче, чем длина соответствующего отрезка, который, как известно из аксиом Евклида, является кратчайшим путем между парой точек. (Точнее, в аксиоматику входит неравенство треугольника — утверждение, что XY + YZ ≥ XZ для любых трёх точек X, Y, Z; этим утверждением мы тоже воспользуемся, буквально на строчку ниже.) Следовательно, длина всей системы дорог не меньше, чем AI + BI + CI + DI. Но из неравенств AI + CI ≥ AC = 1000√2, BI + DI ≥ BD = 1000√2 сразу получаем, что AI + BI + CI + DI ≥ 2000√2, что мы и собирались доказать.

Прочитали? Всё правильно? Поздравляем, у вас вся спина белая.

Допущенная в этом «доказательстве» ошибка столь же проста, сколь и поучительна. Мы погрешили против истины, когда предположили, что от точки пересечения путей (I) к вершинам квадрата ведут четыре разных «направления», то есть четыре разных дорожки. На самом деле это так только в том случае, если пересечение дорожек AC и BD состоит из одной-единственной точки. Но вот как раз это-то и не обязано быть правдой! Даже в том примитивном случае, когда мы просто соединяли дома отрезками (например, AB, BC и CD) и получали путь длины 3000 м, пересечением дорог AC и BD был целый отрезок BC.

Итак, мы просто упустили ещё один вариант (схематически показанный на рис. 5).

Рис. 5.

Здесь какие-то (не показанные на рисунке) дорожки как-то соединяют между собой две левые вершины квадрата и точку I, другие (также не показанные) дорожки соединяют две остальных вершины квадрата и точку O, и, наконец, есть еще дорожки между I и O, показанные красным цветом (можно строго доказать, что любая схема сводится именно к такой, но поскольку точное доказательство оптимальности всё равно выходит за рамки нашей задачи, то и это доказательство мы опустим)

Для рисунка 5 можно повторить наши предыдущие рассуждения, и получить, что сумма длин всех проведенных дорожек не меньше, чем AI + BI + IO + OC + OD. Но может ли эта сумма быть меньше, чем удвоенная диагональ — вот в чём вопрос.

Чтобы ответить на него, нарисуем пример такого соединения «по клеточкам» (рис. 6).

Здесь точки I и O взяты так, чтобы все пунктирные линии шли по гипотенузам прямоугольных треугольников с отношением сторон 3:4:5. (Помните ли вы теорему Пифагора? Из нее следует, что гипотенуза прямоугольного треугольника с катетами 3 и 4 равна ). То есть больший катет (4 клеточки) равен половине стороны квадрата, или 500 м, а меньший (3 клеточки) — 3/4 от 500 м, или 375 м. Поэтому длина каждого пунктирного отрезка равна 5/4 от 500 м, или 625 м, а длина горизонтального красного отрезка — 1/2 от 500 м, или 250 м. Сумма всех показанных отрезков равна 2750 м, то есть меньше, чем 2800.

Рис. 6.

Минимален ли полученный результат? Разумеется, нет. Однако схема соединений, которая к нему приводит, — оптимальна (строгое доказательство мы снова-таки опустим). В рамках этой схемы мы могли бы отыскать еще меньшее значение следующим способом. Пусть a — длина стороны квадрата, а x — длина меньшего катета в прямоугольном треугольнике. Так как больший катет равен a/2, то сумма четырех гипотенуз равна , а красный отрезок равен a – 2x. Даже если вы разучились (или никогда не умели) брать производную и исследовать функцию на экстремумы, для функции это можно легко сделать с помощью сайта wolframalpha.com.

Простой запрос сообщает, что минимум равен 1000(1 + √3) ≈ 2732 м и достигается при x = 500/√3. В «послесловии» мы не только осмыслим этот результат, но и обобщим его.

б) После такой «артиллерийской подготовки» нам будет уже совсем просто разобраться со второй задачей.

Во-первых, покажем, как именно выглядит тетраэдр, развёртку которого мы дали в подсказке 2.

Посмотрите на этот рисунок как на изображение трёхмерного объекта («невидимое» ребро тетраэдра изображено коротким пунктиром) Сравните это с рисунком 2, на котором мы складывали тетраэдр по одному из его ребер (вертикальное ребро на рис. 7) и красной ломаной линии (в проекции, показанной на рис. 7, она прошла бы в точности поверх пунктирного ребра, совсем спрятав его от наших глаз).

Рис. 7.

Итак, мы берем развёртку, сгибаем ее по рёбрам (всем пунктирным линиям на рисунке 3), «склеиваем» между собой две красных линии, две синих, две жёлтых и две пурпурных. После этого развёртка оказывается сложенной так, что две зелёных линии соединены, и осталось только перегнуть их посередине и тоже склеить. Тетраэдр готов.

Как можно было догадаться до такого хитроумного способа? Это не очень трудно; достаточно взглянуть на тот же рисунок как на плоский объект — ромб! Из анализа более простых развёрток ясно, что любая развёртка, сохраняющая нетронутыми две треугольных грани тетраэдра, может рассматриваться как система дорожек, соединяющих четыре вершины этого ромба. Таким образом, задача б) фактически является разновидностью задачи а), только не для квадрата, а для ромба. Все, что было сказано в нашем софизме, можно повторить и здесь. Если мы хотим получить систему отрезков, более короткую, чем сумма двух диагоналей ромба, то ни в какой внутренней точке не должны сходиться четыре разных отрезка, а значит, нужно попытаться построить соединения аналогично тому, как мы это сделали в задаче а).

Собственно, вместо того, чтобы подбирать нужные вспомогательные точки «по клеточкам», я еще раз воспользуюсь проверенным WolframAlpha. Только перед этим все-таки нужно немножко подготовиться — ввести на нашем рисунке систему координат.

Пусть началом координат O будет точка пересечения диагоналей ромба ABCD. Так как ромб составлен из двух правильных треугольников со стороной 10 см, то меньшая диагональ ромба тоже равна 10 см, а половина большей диагонали может быть вычислена с помощью теоремы Пифагора: . Поэтому координаты вершин A и C ромба — (±5, 0), а координаты вершин B и D — (0, ±5√3). Если взять одну (неизвестную) вспомогательную точку с координатами (x, y), то координаты второй (симметричной ей относительно начала координат) точки будут, естественно, (−x, −y).

Все та же теорема Пифагора подсказывает нам, что минимизировать нужно значение такой функции:

(эти знаки корней — длины отрезков от нашей вспомогательной точки до вершин ромба и длина отрезка от нее же до начала координат, то есть половина отрезка между вспомогательными точками). Грязную работу за нас делает машина:

Рис. 8.

Обычно WolframAlpha «демонстрирует» узнавание тех рациональных и иррациональных чисел, которые она узнала. Но тут, видать, что-то у нее не сложилось. Тем не менее, мы предъявим те же самые числа в другом виде: x = 10/7, y = 5/(7√3), а минимальное значение точно равно 10√7. И если корни из 3 здесь еще как-то можно было ожидать, то появление в ответе корня из 7 выглядит абсолютнейшей загадкой. Если вы готовы ее поразгадывать ещё какое-то время — подумайте, а если уже сдались, то можно читать послесловие.

Отцами этой задачи можно считать разных людей из разных эпох. Одним из первых был знаменитый математик-любитель Пьер Ферма (по основной профессии он был юристом), который в качестве примера применения метода исследования экстремумов предложил следующую задачу:

Тот же, кто этот метод не оценил, пусть решит: для заданных трех точек найти такую четвертую, что если из нее провести три отрезка в данные точки, то сумма этих трех отрезков даст наименьшую величину.

Обратите внимание, что задача сформулирована на «геометрическом» языке, хотя автор предполагал исключительно «аналитическое» решение. Тем не менее, после Ферма последовали и чисто геометрические решения. Подробнее о них можно прочитать в §3 книги В. Протасова «Максимумы и минимумы в геометрии». Поскольку почти одновременно с Ферма (и, судя по всему, независимо от него) этой задачей занимался другой замечательный исследователь — Эванджелиста Торричелли, то точку, которую необходимо отыскать в этой задаче, сейчас принято называть точкой Торричелли–Ферма.

Спустя много лет (уже в XX веке) Ярник и Кёсслер сформулировали обобщение этой задачи, в котором три точки были заменены произвольным числом точек. А именно, их задача состоит в описании связных плоских графов наименьшей длины, проходящих через данное конечное множество точек плоскости. Возможно, их статья, опубликованная в не самом популярном математическом журнале, да еще и на польском языке, прошла бы незамеченной, но ссылка на неё вошла в знаменитую книгу Р. Куранта и Г. Роббинса «Что такое математика?»:

Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни системой дорог таким образом, чтобы их общая протяженность была минимальной. <...> Было бы естественно обобщить эту проблему на случай нескольких заданных точек следующим образом: требуется найти в плоскости такую точку, чтобы сумма расстояний от нее до данных точек обращалась в минимум. <...> Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной.

С лёгкой руки Куранта задача поиска минимальной сети нынче называется геометрической задачей Штейнера, хотя сам Якоб Штейнер (вообще-то правильной транскрипцией этой немецкой фамилии является «Штайнер», но в русской математической литературе сложилась традиция называть его Штейнером) такую задачу не ставил и не решал.

Тем не менее, в рамках исследования задачи Ферма — Торричелли — Штейнера несложно доказать следующие замечательные свойства сетей Штейнера:
1) В кратчайшую сеть, кроме данных (исходных) точек, могут входить вспомогательные.
2) В каждой вспомогательной точке сходятся три отрезка, причем все попарные углы между ними равны 120°.
3) Для ряда частных случаев полученную сеть можно «спрямить», то есть превратить в равновеликий ей отрезок.

Рис. 9.

Пример такого спрямления для сети, соответствующей ромбу из двух правильных треугольников (рис. 7), показан на рисунке 9. Отсюда уже совсем несложно получить этот непостижимый корень из 7: действительно, левый верхний конец спрямлённого отрезка имеет координаты (−1, √3/2), правый нижний — координаты (1, −√3/2), поэтому длина отрезка равна . Осталось только показать, почему такое спрямление возможно.

Для этого посмотрим на правильный треугольник RST, изображенный на рисунке 10.

Теорема. Если U — произвольная точка дуги RS окружности, описанной около этого треугольника, то UT = UR + US (в других обозначениях, l = m + n).

Доказательство. Повернём U и S вокруг точки R на угол 60 градусов. Поскольку величина угла поворота совпадает с углом правильного треугольника, то точка S при таком повороте перейдёт в T, а точка U перейдёт в третью вершину правильного треугольника RUV, то есть такую точку, для которой UV = m и угол RUV = 60°. Но эта точка лежит на отрезке UT, потому что угол RUT — вписанный угол, опирающийся на дугу RT, — равен вписанному углу RST, то есть 60°. Таким образом, отрезок US после поворота переходит в отрезок VT. Откуда VT = n, а так как UV = m и UT = l, то l = m + n. Теорема доказана.

Рис. 10.

Свойство 2) сетей Штейнера утверждает, что угол между красным и синим отрезками на рисунке 9 равен 120°. Это означает, что он опирается на дугу 240°, то есть лежит на окружности, описанной вокруг правильного треугольника. Таким образом, спрямление на рисунке 8 — не что иное, как применение этой теоремы для замены суммы двух отрезков (красного и синего, а также жёлтого и пурпурного) одним.

Ровно то же самое можно проделать и для сети дорог в задаче а). А фактически тем же способом можно и строго доказать, что в задачах а) и б) мы действительно получили минимальные сети Штейнера.

Несмотря на долгую историю, исследования задачи о сетях Штейнера в наши дни продолжаются — разумеется, уже с помощью компьютеров. Вот всего несколько ссылок.
1) Программный пакет GeoSteiner предназначен для решения задачи Штейнера для системы точек плоскости.
2) Огромная коллекция различных вариаций задачи Штейнера и сведений об имеющихся алгоритмах их решения.
3) Henry Bottomley исследовал для правильных многогранников несколько близких задач. Например, такая вот головоломка: чему равна длина кратчайшего замкнутого пути по поверхности тетраэдра, пересекающего каждое его ребро? А то же самое для куба?
4) Обобщение задачи о минимальной развёртке на другие правильные многогранники.

Автор благодарен сайту braingames.ru, на котором он узнал условие пункта б).