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

Проект МЦНМО
при участии
школы 57
Задача 98294
Темы:    [ Ломаные ]
[ Вписанные и описанные многоугольники ]
[ Подсчет двумя способами ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Рассматриваются всевозможные шестизвенные замкнутые ломаные, все вершины которых лежат на окружности.
  а) Нарисуйте такую ломаную, которая имеет наибольшее возможное число точек самопересечения.
  б) Докажите, что большего числа самопересечений такая ломаная не может иметь.


Решение

  а) На рисунке изображена шестизвенная ломаная с семью точками самопересечения.

  б) Докажем, что такая ломаная не может иметь больше семи самопересечений. Пусть общее число самопересечений равно N. Для каждого звена рассмотрим число точек самопересечения, которые лежат на этом звене, и обозначим через S сумму этих чисел. Тогда  S ≥ 2N  (если в одной точке пересекаются два звена, то эта точка входит в сумму дважды, если три или больше — больше двух раз). На каждом звене может лежать не больше трёх точек самопересечения, так как кроме этого звена и двух соседних с ним имеются всего три звена, которые могут с ним пересекаться. При этом три точки могут быть только на "диагональном" звене: таком, что из четырёх вершин, не являющихся его концами, две лежат в одной полуплоскости от него, а две другие – в другой. (Если по какую-то сторону от звена лежит лишь одна вершина, то нельзя провести больше двух отрезков к вершинам, лежащим по другую сторону звена.) Таких "диагональных" звеньев максимум три. На каждом из остальных лежат не больше чем по две точки самопересечения, поэтому  S ≤ 3· 2 + 3·3 = 15,  то есть  NS/2 ≤ 7,5.

Замечания

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

2. В Задачнике "Кванта" задача была в следующей формулировке.
  Вершины шестизвенной замкнутой ломаной лежат на окружности. Какое наибольшее число точек самопересечения может иметь такая ломаная?

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

журнал
Название "Квант"
год
Год 1996
выпуск
Номер 4
Задача
Номер М1551
олимпиада
Название Турнир городов
Турнир
Дата 1995/1996
Номер 17
вариант
Вариант весенний тур, тренировочный вариант, 8-9 класс
Задача
Номер 4

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

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