Комбинаторная геометрия → .04 Разрезания и геометрические конструкции в текстовых

Рассмотрим один из квадратов и два перпендикулярных разреза через центр пересекающие его стороны в точках

Повернем картинку на градусов в точке Тогда точка останется на месте. Заметим, что Значит, и так как центр квадрата, то и Значит, треугольники и равны и переходит в при повороте. Так как при повороте переходит в в то имеем, что и они переходят друг в друга поворотом. Получаем, что четырехугольники равны и переходят друг в друга поворотом. Аналогично заключаем для остальных частей на которые делят квадрат разрезы.

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

Заметим, что если два квадрата из девяти находятся в одной горизонтальной строке, то они имеют одинаковую высоту, а будучи квадратами — и одинаковую ширину, так что в этом случае всё доказано. Аналогично в случае с вертикальным столбцом.

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

Действительно, тогда квадраты попадают в девять столбцов из десяти и в девять строк из десяти, и остаётся одна свободная строка и один свободный столбец, но тогда прямоугольник, стоящий на пересечении ”свободной” строки и ”свободного” столбца, будет ещё одним, десятым квадратом. В самом деле, ширину свободного столбца можно найти, вычтя суммарную ширину девяти квадратов из ширины большого квадрата. Точно так же высота свободной строки равна разности высоты большого квадрата и суммы высот девяти квадратов, а высота любого квадрата равна его ширине. Но по условию десятого квадрата нет, так что третий случай невозможен.

(a) Проведем доказательство индукцией по База для тривиальна. Пусть в угольнике с помощью flip-ов можно получить все триангуляции. Докажем это утверждение для угольника. Пусть — наш угольник. Заметим, что проведена хотя бы одна диагональ Иначе, если ни одной такой диагонали не проведено, то найдется диагональ где Рассмотрим диагональ между вершинами с минимальным Тогда между вершинами не проведено ни одной диагонали. Так как то получаем, что наше разбиение многоугольника диагоналями не является триангуляцией — противоречие. Итак, хотя бы одна диагональ проведена между вершинами для некоторого Она отсекает от нашего многоугольника треугольник Весь многоугольник без этого треугольника обозначим (он получается удалением вершины из и ребер, соединенных с ней). Тогда — выпуклый угольник. Любое его разбиение может быть получено flip-ами треугольников в его триангуляции. Вернемся к многоугольнику С помощью нескольких flip-ов можно вместо диагонали получить любую диагональ Если такая диагональ получена, то рассуждения о получении триангуляций с этой диагональю аналогичны рассуждениям с диагональю Таким образом, любая триангуляция получится, поскольку любая триангуляция содержит диагональ между некоторыми вершинами и

(b) Рассмотрим соседние вершины и Обозначим через разбиение, в котором все диагонали выходят из вершины а через — разбиение, в котором все диагонали выходят из Заметим, что в ни одна диагональ не выходит из Поскольку за одну перестройку добавляется не более одной диагонали, выходящей из то для преобразования в требуется не менее перестроек.

(c) Предположим, что мы хотим преобразовать в где и — два произвольных разбиения. Пусть — вершшна, из которой выходит хотя бы одна диагональ — перестройка, определенная в (b). Покажем, что можно преобразовать в добавляя при каждой перестройке по одной диагонали, выходящей из Пусть диагональ ещё не проведена. Тогда её начало принадлежит одному из треугольников разбиения, причем — диагональ. Поэтому к ней с другой стороны прилегает некий треугольник разбиения ( может совпадать с Сделав flip четырёхугольника мы добавим диагональ Итак, для указанного преобразования нужно не более перестроек. Для преобразования в необходимо столько же flip-oв, сколько для обратного преобразования в то есть не более поскольку одна диагональ уже стоит на своём месте.

Чтобы решить эту задачу, перерисуем картинку на клетчатом листе бумаги. Легко видеть, что внутри синего контура находится кирпичей.