|
|
 |
Условие
Многоугольник можно разбить на 100 прямоугольников, но нельзя – на 99. Докажите, что его нельзя разбить на 100 треугольников.
Решение
Заметим, что каждые два прямоугольника разбиения имеют параллельные стороны (можно считать, что горизонтальные и вертикальные). Поэтому количество сторон нашего многоугольника чётно (его горизонтальные и вертикальные стороны чередуются).
Лемма. Если 2k-угольник можно разбить на прямоугольники, то его можно разбить на не более чем k – 1 прямоугольник.
Доказательство. Сумма углов многоугольника S = (2k – 2)180°, и все углы в нём равны 90°
или 270°. Если все они по 90°, то это прямоугольник.
Пусть найдётся угол A в 270°. Продолжим одну из его сторон
внутрь многоугольника до пересечения с контуром. Многоугольник разобьётся на две части, причём сумма внутренних углов частей не превосходит суммы внутренних углов многоугольника (продолжение стороны отрезает от угла A угол в 90°, который попадает в одну из частей, и угол в 180°, который лежит на стороне другой части, поэтому исчезает; в то же время дополнительно в этих
частях могут возникнуть только два угла по 90° там, где продолжение стороны дошло до контура многоугольника).
Заметим, что общее количество углов в 270° уменьшилось. Если они еще остались, будем повторять операцию с частями. В конце мы получим n частей без углов 270°, то есть n прямоугольников с общей суммой углов
S = 360°n ≤ (2k – 2)180°, откуда
n ≤ k – 1.
Из леммы следует, что в нашем многоугольнике число вершин больше 200, иначе его можно разбить на 99 прямоугольников. Разобьём его на m треугольников и рассмотрим сумму их углов: S = 180°m. Найдём теперь S, учитывая, что углы треугольников входят в состав углов многоугольника. Каждый угол многоугольника даёт вклад не менее 90° (из угла 270° может быть вычтено 180°, если его вершина лежит на стороне какого-нибудь треугольника), поэтому S = 180°m > 200·90°, откуда m > 100, что и требовалось.
Замечания
Оценка в задаче является точной: объединение клеток квадрата 100×100, кроме клеток, лежащих выше главной диагонали, даёт пример многоугольника, который главной диагональю разбивается на 101 треугольник.
