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

Проект МЦНМО
при участии
школы 57
Задача 109579
Темы:    [ Выпуклая оболочка и опорные прямые (плоскости) ]
[ Индукция в геометрии ]
[ Выпуклые многоугольники ]
[ Обход графов ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Внутри круга расположены точки A1, A2, ..., An, а на его границе – точки B1, B2, ..., Bn так, что отрезки A1B1, A2B2, ..., AnBn не пересекаются. Кузнечик может перепрыгнуть из точки Ai в точку Aj, если отрезок AiAj не пересекается ни с одним из отрезков AkBk,  k ≠ i, j.
Докажите, что за несколько прыжков кузнечик сможет попасть из каждой точки Ap в любую точку Aq.

Решение

  Индукция по n. База (n ≤ 2)  очевидна.
  Шаг индукции. Пусть  n ≥ 3.  Без ограничения общности можно считать, что многоугольник M с вершинами A1, A2, ..., Ak есть выпуклая оболочка множества точек A1, A2, ..., An. Рассмотрим отрезки вида AmBm  (1 ≤ m ≤ k),  пересекающие M более чем в одной точке. Обозначим через Cm вторую точку пересечения отрезка AmBm с контуром M. Тогда отрезки AmCm не пересекаются. Рассмотрим один из них и одну из частей M, на которые его делит AmCm. Тогда в ней найдётся такой отрезок ApСp , что на части контура от Ap до Сp нет других точек Сq. Тогда там есть ещё одна точка Ai, причём AiBi не пересекает контур M. Аналогично в другой части найдётся такая точка Aj, что отрезок AjBj не пересекает контур M. Таким образом, отрезки AiBi и AjBj не пересекают отрезков ApAq при  p, q ≠ i.  Применив предположение индукции к  n – 1  отрезку  A1B1, A2B2, ..., Ai–1Bi–1, Ai+1Bi+1, ..., AnBn,  получаем, что точки A1, A2, ..., Ai–1, Ai+1, ..., An можно соединить прыжками кузнечика. То же верно и в отношении точек A1, A2, ..., Aj–1, ..., Aj+1, ..., An. Наконец, и точки Ai и Aj также связаны прыжками кузнечика: из точки Ai можно добраться до точки As,  s ≠ i, j,  а из точки As – до точки Aj.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1994
Этап
Вариант 4
класс
Класс 11
задача
Номер 94.4.11.8

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

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