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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Спроектируем все отмеченные отрезки на одну из сторон квадрата. Если она полностью покрыта проекциями, то их суммарная длина не меньше Если на стороне есть точка, не покрытая проекциями, то проведём через неё перпендикуляр к стороне. Этот перпендикуляр покрыт прямоугольниками, в которых отмечена сторона, параллельная ему (иначе основание перпендикуляра покрыто проекцией отмеченной стороны), значит, суммарная длина этих отрезков равна

Максимальное число вершин у имеющихся многоугольников возрастает, только если от -угольника отрезать треугольник, и останется -угольник. Если раз так сделать, получится треугольников. Если же так сделать не более раз, то получится максимум угольник. Продолжая разрезания достаточно долго так, чтобы треугольников появилось не более мы получим много многоугольников с числом вершин от до После того, как будет ещё сделано более разрезаний, у нас окажется многоугольников какого-то вида.

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

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

Таким образом, первый игрок выигрывает, если нечетно, то есть четно, второй — во всех остальных случаях.

Назовем рб.триангуляцией правильного -угольника триангуляцию, в которой все треугольники являются равнобедренными. Пусть

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Для любого натурального

Доказательство. Рассмотрим строну правильного -угольника. После разбиения она должна быть включена некоторый в равнобедренный треугольник Далее рассмотрим два варианта

1.

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

2.

является ребром Тогда третья вершина является одной из соседних к концу вершинам.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к исходному доказательству. Разобьем натуральный ряд на множества для всех нечетных Каждое число попадет в некоторое из данных множеств, причем ровно один раз. Заметим, что, в силу леммы на всех элементах некоторого из данных множеств значения функции равны между собой, а, значит, нам достаточно решать исходную задачу лишь для нечетных

______________________________________________________________________________________________________________________________________________________

Лемма 2. Если при некотором натуральном то рб.триангуляция существует тогда и только тогда, когда

при некотором натуральном

Доказательство. Поскольку нечетно существует по крайней мере одна сторона такая, что она образует треугольник не с соседней стороной многоугольника, а, значит, является основанием некоторого треугольника в триангуляции.

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

Таким образом, исходный многоугольник разбивается на на два -сектора. Основание -сектора не может являться ребром некоторого треугольника, то есть является его основанием, следовательно, триангуляция существует только тогда, когда существует вершина на серединном перпендикуляре к основанию, то есть когда кратно

Так, каждый из -секторов разбивается на два -сектора, для каждого из которых верны рассуждения выше, пока сектор не будет содержать одну сторону. Тем самым, при некотором натуральном

Из данных рассуждений однозначно строится пример для любого

_________________________________________________________________________________________________________________________________________________________________________________

Таким образом, любой -многоугольник имеет рб.триангуляцию тогда и только тогда, когда причем для некоторого натурального а, значит, для некоторого натурального

Пример:

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

Рассмотрим пример, подходящий под условие, с максимальным количеством кубов. Выберем из всех кубов в этом примере наибольший куб пусть его сторона равна и при этом Тогда заменим этот куб на куб со стороной лежащий строго внутри Покажем, почему новый пример также подходит под все условия. Во-первых, куба в примере еще не было, так как иначе лежал строго внутри Далее, если какой-то куб лежит строго внутри то и до этого куб лежал внутри куба что противоречит условию. Пусть, наоборот, сам куб лежит внутри какого-то куба Тогда сторона этого куба не меньше с другой стороны, максимальная сторона всех кубов, поэтому сторона в точности равна Но единственный куб со стороной строго внутри которого лежит это собственно куб а мы его из примера удалили. Поэтому такая ситуация невозможна, и значит новый набор кубов также подходит под все условия. Будем описанным выше образом заменять кубы на меньшие, пока не закончатся кубы со сторонами, большими В конце стороны всех кубов будут равны или а таких кубов не больше Осталось убедиться, что набор всех кубов со сторонами и очевидно, подходит под условие задачи, значит, ответ в точности

Рассмотрим вершину квадрата. Отрежем от квадрата эту вершину, проведя разрез близко к вершине. Мы получим маленький треугольник, а количество вершин у оставшейся фигуры увеличится на одну. Сделаем так с каждой вершиной квадрата. Мы получим четыре треугольника и один восьмиугольник — в точности то, что и требовалось по условию.

Решение

Отметим у квадрата по две точки на каждой стороне и еще по одной точке недалеко от каждой стороны. Проведем отрезки так, как показано на рисунке. Вырежем получившихся треугольника. Тогда оставшаяся фигура — -угольник, значит, мы получили искомое разрезание.

Посмотрим на вершины -угольника. Каждая из этих вершин должна являться также вершиной либо исходного квадрата, либо одного из треугольников, на которые мы разрезали исходный квадрат. У квадрата вершины, у четырех треугольников вершин. В сумме получается вершин. Значит, у -угольника останется вершина, не совпадающая ни с вершиной квадрата, ни с вершиной треугольника. Тогда угол при ней равен , что противоречит определению вершины многоугольника. Мы пришли к противоречию, значит, указанное разрезание невозможно.

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

Докажем теперь, что большее количество вырезать не получится. Действительно, разобъём кубик на “диагональные” слои (см.картинку ниже), которые раскрасим по циклу в 4 цвета. Несложно убедится, что в каждом параллелепипеде содержится ровно 1 кубик каждого цвета. При этом заметим, что при разбиении из примера у нас остался угловой куб размера , в котором присутствуют только кубики трёх цветов. Значит, существует цвет, в который покрашено ровно 52 кубика, поэтому не получится вырезать параллелепипедов больше этого количества.

Заметим, что красных сливок , так как при разрезании получается на одну часть больше, чем было сделано разрезов. Тогда желтых сливок , а зеленых — . То есть всего сливок , но тогда при разрезании по всем сливкам получится части торта.

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

Способ 1.

В большом кубе помещается маленьких кубика. Из них кубиков с тремя окрашенными гранями — 8, так как углов.

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

Граней у куба . И на каждой грани помещается маленьких кубика с одной окрашенной гранью. Поэтому маленьких кубиков с одной окрашенной гранью .

Значит, неокрашенных кубиков .

Способ 2.

Кубик состоит из четырех горизонтальных слоев размера . Если отрезать верхний и нижний слои (все кубики которых окрашены красной краской), то останется два слоя, опоясаных кубиками, окрашенными красной краской.

Если убрать окрашенные кубики (а именно они здесь окрашены в красный цвет), то останется кубик со сторой . В нем помещается восемь маленьких кубиков.

Пусть в равнобедренной трапеции с основаниями проведена диагональ так что первый жук ползает по циклу второй — по циклу

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

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

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

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

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

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

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

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

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

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

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

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

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