|
|
 |
Условие
Внутри круга расположены точки 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.
