Разделы 
Дополнительно
Задача по математике - 1869
2019-01-21 
Многоугольник можно разбить на 100 прямоугольников, но нельзя - на 99. Докажите, что его нельзя разбить на 100 треугольников.
Решение:
Заметим, что количество сторон нашего многоугольника четно, так как его горизонтальные и вертикальные стороны чередуются.
Лемма. Если $2k$-угольник можно разбить на прямоугольники, то его можно разбить на не более чем $k - 1$ прямоугольник.
Доказательство. Сумма углов многоугольника $S = (2k - 2) \cdot 180^{\circ}$, и все углы в нем, очевидно, по $90^{\circ}$ или по $270^{\circ}$. Если все по $90^{\circ}$, то это прямоугольник. Пусть найдется угол $A$ в $270^{\circ}$. Продолжим одну из его сторон внутрь многоугольника до пересечения с контуром. Многоугольник разобьется на две части, причем сумма внутренних углов частей не превосходит суммы внутренних углов многоугольника (продолжение стороны отрезает от угла $A$ угол в $90^{\circ}$ , который попадает в одну из частей, и угол в $180^{\circ}$, который лежит на стороне другой части, поэтому исчезает; в то же время дополнительно в этих частях могут возникнуть только два угла по $90^{\circ}$ там, где продолжение стороны дошло до контура многоугольника). Заметим, что общее количество углов в $270^{\circ}$ уменьшилось. Если они еще остались, будем повторять операцию с частями. В конце мы получим $n$ частей без углов $270^{\circ}$, т. е. $n$ прямоугольников с общей суммой углов $S = 360^{\circ} \cdot n < (2k - 2) \cdot 180^{\circ}$, откуда $n \leq k - 1$. Лемма доказана.
Из леммы следует, что в нашем многоугольнике число вершин больше 200, иначе его можно разбить на 99 прямоугольников. Разобьем его на m треугольников и рассмотрим сумму их углов: $S = 180^{\circ}m$. Найдем теперь $S$, учитывая, что углы треугольников входят в состав углов многоугольника. Каждый угол многоугольника дает вклад не менее $90^{\circ}$ (из угла $270^{\circ}$ может быть вычтено $180^{\circ}$, если его вершина лежит на стороне какого-нибудь треугольника), поэтому $S = 180^{\circ} \cdot m > 200 \cdot 90^{\circ}$ , откуда $m > 100$, что и требовалось доказать.
Замечание. Оценка в задаче является точной: объединение клеток квадрата $100 \times 100$, кроме клеток, лежащих выше главной диагонали, дает пример многоугольника, который главной диагональю разбивается на 101 треугольник.
Многоугольник можно разбить на 100 прямоугольников, но нельзя - на 99. Докажите, что его нельзя разбить на 100 треугольников.
Решение:
Заметим, что количество сторон нашего многоугольника четно, так как его горизонтальные и вертикальные стороны чередуются.
Лемма. Если $2k$-угольник можно разбить на прямоугольники, то его можно разбить на не более чем $k - 1$ прямоугольник.
Доказательство. Сумма углов многоугольника $S = (2k - 2) \cdot 180^{\circ}$, и все углы в нем, очевидно, по $90^{\circ}$ или по $270^{\circ}$. Если все по $90^{\circ}$, то это прямоугольник. Пусть найдется угол $A$ в $270^{\circ}$. Продолжим одну из его сторон внутрь многоугольника до пересечения с контуром. Многоугольник разобьется на две части, причем сумма внутренних углов частей не превосходит суммы внутренних углов многоугольника (продолжение стороны отрезает от угла $A$ угол в $90^{\circ}$ , который попадает в одну из частей, и угол в $180^{\circ}$, который лежит на стороне другой части, поэтому исчезает; в то же время дополнительно в этих частях могут возникнуть только два угла по $90^{\circ}$ там, где продолжение стороны дошло до контура многоугольника). Заметим, что общее количество углов в $270^{\circ}$ уменьшилось. Если они еще остались, будем повторять операцию с частями. В конце мы получим $n$ частей без углов $270^{\circ}$, т. е. $n$ прямоугольников с общей суммой углов $S = 360^{\circ} \cdot n < (2k - 2) \cdot 180^{\circ}$, откуда $n \leq k - 1$. Лемма доказана.
Из леммы следует, что в нашем многоугольнике число вершин больше 200, иначе его можно разбить на 99 прямоугольников. Разобьем его на m треугольников и рассмотрим сумму их углов: $S = 180^{\circ}m$. Найдем теперь $S$, учитывая, что углы треугольников входят в состав углов многоугольника. Каждый угол многоугольника дает вклад не менее $90^{\circ}$ (из угла $270^{\circ}$ может быть вычтено $180^{\circ}$, если его вершина лежит на стороне какого-нибудь треугольника), поэтому $S = 180^{\circ} \cdot m > 200 \cdot 90^{\circ}$ , откуда $m > 100$, что и требовалось доказать.
Замечание. Оценка в задаче является точной: объединение клеток квадрата $100 \times 100$, кроме клеток, лежащих выше главной диагонали, дает пример многоугольника, который главной диагональю разбивается на 101 треугольник.
