Один раз отрежь

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

На рисунках ниже показано, как нужно складывать фигуры из условия задачи, чтобы потом вырезать каждую из них одним разрезом.

С треугольником более-менее все понятно: складываем по одной биссектрисе, потом — по другой (рис. 1).

Рис. 1. Вырезание правильного треугольника одним разрезом. Рисунок из книги J. O'Rourke How to Fold It: The Mathematics of Linkages, Origami and Polyhedra

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

Рис. 2. Вырезание правильной пятиконечной звезды одним разрезом. Рисунок из статьи E. D. Demaine et al., 1998. Folding and Cutting Paper

С лебедем сложнее всего. Это понятно: фигура без симметрий, с большим числом сторон; поэтому потребуется большое число складок. Схема, по которой надо складывать, изображена на рис. 3. Простые пунктирные линии изображают складки «вниз», пунктиры точка-тире изображают складки «вверх». Сначала нужно наметить эти складки по отдельности, чтобы лист приобрел форму крыши дома, а только потом складывать лист в плоскую фигуру.

Рис. 3. Схема складывания лебедя. Простые пунктирные линии изображают складки «вниз», пунктиры точка-тире изображают складки «вверх». Схема с сайта erikdemaine.org

На серии фотографий показан весь процесс складывания:

Рис. 4. Пошаговое складывания лебедя и вырезание его одним разрезом. Фотографии с сайта uk.wikipedia.org

О том, откуда возникает такая хитроумная система складок, читайте в послесловии.

Все предложенные в условии варианты — это всего лишь частные случаи общего вопроса, который звучит так:

Дан многоугольник на плоском листе бумаги, можно ли так сложить этот лист, чтобы многоугольник можно было вырезать одним прямым разрезом?

Оказывается, вне зависимости от формы многоугольника, ответ на этот вопрос всегда положительный: да, можно. (Разумеется, мы сейчас обсуждаем эту задачу с точки зрения математики и не касаемся «физической» стороны дела: слишком много раз лист бумаги невозможно сложить. Считается, что даже очень тонкую бумагу больше 7-8 раз перегнуть невозможно. Это почти так: при некотором старании можно сделать 12 перегибов, но больше уже вряд ли получится.)

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

Пусть на листе бумаги нарисован произвольный граф. Тогда этот лист можно сложить так, чтобы данный граф можно было вырезать одним разрезом, и ничего лишнего вырезано не будет.

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

Вкратце суть такова. Сначала мы должны построить прямолинейный скелет (straight skeleton). Это набор линий — траекторий вершин исходного многоугольника, — по которым они движутся при его специальном сжатии. Сжатие устроено так: мы двигаем стороны многоугольника «внутрь» с постоянной скоростью, чтобы при этом каждая сторона двигалась, не меняя своего направления. Как несложно убедиться, поначалу вершины будут ползти по биссектрисам углов многоугольника. То есть эта на первый взгляд странная конструкция просто обобщает идею, предложенную в подсказке: что надо стараться складывать по биссектрисам углов многоугольника. Отметим, что в процессе сжатия многоугольник может «развалиться» на части, как это произошло на рис. 5.

Рис. 5. Построение прямолинейного скелета. Рисунок с сайта en.wikipedia.org

После того как скелет получен, из каждой его вершины нужно провести лучи, перпендикулярные к тем сторонам исходной фигуры, к которым их можно провести. Если луч натыкается на линию из скелета, то после пересечения он должен продолжиться не прямо, а вдоль своего зеркального отражения относительно этой линии. Система складок состоит из проведенных линий.

Подробнее об этом и о том, как определять направление складки («вверх» или «вниз»), можно прочитать в статье E. D. Demaine, M. L. Demaine, A. Lubiw, 1998. Folding and Cutting Paper. Краткую историю и еще один подход к решению задачи можно найти на страничке Эрика Демейна, одного из авторов доказательства теоремы. Также можно почитать чуть более популярный рассказ об этой теореме (к сожалению, тоже на английском). Ну и наконец, советую посмотреть мультфильм «Математических этюдов», в котором прекрасно видно, как нужно складывать треугольник и звезду, чтобы потом вырезать их одним разрезом.

Напоследок отмечу, что вопросы, подобные обсуждавшимся выше, поднимались уже довольно давно. Например, в японской книге 1721 года в качестве одной из задачек читателям предлагалось вырезать одним разрезом фигурку из трех объединенных ромбов (рис. 6). Позже метод вырезания звезды объяснял в своей книге знаменитый иллюзионист Гарри Гудини. Кстати, по легенде, как раз благодаря тому, что такую звезду можно быстро вырезать из бумаги или ткани, сейчас на флаге США мы видим именно пятиконечные звезды: швея Бетси Росс, которая, по преданию, сшила первый флаг, смогла убедить Джорджа Вашингтона, что их лучше использовать для флага, чем шестиконечные, которые изначально хотел использовать Вашингтон.

Рис. 6. Задача из японской книги 1721 года. Рисунок с сайта erikdemaine.org