ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109648
Темы:    [ Разрезания на части, обладающие специальными свойствами ]
[ Перестройки ]
[ Сумма внутренних и внешних углов многоугольника ]
[ Произвольные многоугольники ]
[ Четность и нечетность ]
Сложность: 5-
Классы: 10
В корзину
Прислать комментарий

Условие

Многоугольник можно разбить на 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 треугольник.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1997
Этап
Вариант 5
Класс
Класс 10
задача
Номер 97.5.10.4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .