Разделы 
Дополнительно
Задача по математике - 1467
2019-01-03 
Внутри круга расположены точки $A_{1}$, $A_{2}$, $\cdots$ , $A_{n}$, а на его границе – точки $B_{1}$, $B_{2}$, $\cdots$ , $B_{n}$ так, что отрезки $A_{1} B_{1}$, $A_{2} B_{2}$, $\cdots$ , $A_{n} B_{n}$ не пересекаются. Кузнечик может перепрыгнуть из точки $A_{i}$ в точку $ A_{j}$, если отрезок $A_{i} A_{j}$ не пересекается ни с одним из отрезков $A_{k} B_{k}$, $k \neq i, j$. Докажите, что за несколько прыжков кузнечик сможет попасть из любой точки $A_{p}$ в любую точку $A_{q}$.
Решение:
Будем решать задачу индукцией по $n$. При $n \leq 2$ утверждение задачи очевидно. Пусть теперь $n \geq3$. Без ограничения общности можно считать, что многоугольник $M$ с вершинами $ A_{1}$, $ A_{2}$, $\cdots$ , $ A_{k}$ есть выпуклая оболочка множества точек $A_{1}$, $ A_{2}$, $\cdots$ , $ A_{n}$.
Рассмотрим отрезки вида $A_{m} B_{m} \left ( 1\leq m\leq k \right )$, пересекающие $M$ более чем в одной точке. Обозначим через ${A}^{ \prime}_{m}$ вторую точку пересечения отрезка $ A_{m}B_{m}$ с контуром $M$. Тогда отрезки $A_{m}{A}^{ \prime}_{m}$ не пересекаются. Рассмотрим один из них и одну из частей $M$, на которые его делит $A_{m}{A}^{ \prime}_{m}$. Тогда в ней найдется такой отрезок $A_{p}{A}^{ \prime}_{p}$, что на части контура от $A_{p}$ до ${A}^{ \prime}_{p}$ нет других точек ${A}^{ \prime}_{q}$. Тогда там есть еще одна точка ${A}_{i}$, причем ${A}_{i}{B}_{i}$ не пересекает контур $M$. Аналогично, в другой части найдется точка ${A}_{j}$ такая, что отрезок ${A}_{j}{B}_{j}$ не пересекает контур $M$ рис.
Таким образом, отрезки ${A}_{i}{B}_{i}$ и ${A}_{j}{B}_{j}$ не пересекают отрезков ${A}_{p}{A}_{q}$ при $p,q \neq i$.
Применив предположение индукции к $\left ( n-1 \right )$ отрезку ${A}_{1}{B}_{1}$, ${A}_{2}{B}_{2}$, $\cdots$, ${A}_{i-1}{B}_{i-1}$, ${A}_{i+1}{B}_{i+1}$, …, ${A}_{n}{B}_{n}$, получаем, что точки ${A}_{1}$, ${A}_{2}$, $\cdots$, ${A}_{i-1}$, ${A}_{i+1}$, $\cdots$, ${A}_{n}$ можно соединить прыжками кузнечика. То же верно и в отношении точек ${A}_{1}$, ${A}_{2}$, …, ${A}_{j-1}$, ${A}_{j+1}$, $\cdots$, ${A}_{n}$. Наконец, и точки ${A}_{i}$ и ${A}_{j}$ также связаны прыжками кузнечика: из точки ${A}_{i}$ можно добраться до точки ${A}_{s}$, $s \neq I,j$, а из точки ${A}_{s}$ - до точки ${A}_{j}$.
Внутри круга расположены точки $A_{1}$, $A_{2}$, $\cdots$ , $A_{n}$, а на его границе – точки $B_{1}$, $B_{2}$, $\cdots$ , $B_{n}$ так, что отрезки $A_{1} B_{1}$, $A_{2} B_{2}$, $\cdots$ , $A_{n} B_{n}$ не пересекаются. Кузнечик может перепрыгнуть из точки $A_{i}$ в точку $ A_{j}$, если отрезок $A_{i} A_{j}$ не пересекается ни с одним из отрезков $A_{k} B_{k}$, $k \neq i, j$. Докажите, что за несколько прыжков кузнечик сможет попасть из любой точки $A_{p}$ в любую точку $A_{q}$.
Решение:
Будем решать задачу индукцией по $n$. При $n \leq 2$ утверждение задачи очевидно. Пусть теперь $n \geq3$. Без ограничения общности можно считать, что многоугольник $M$ с вершинами $ A_{1}$, $ A_{2}$, $\cdots$ , $ A_{k}$ есть выпуклая оболочка множества точек $A_{1}$, $ A_{2}$, $\cdots$ , $ A_{n}$.
Рассмотрим отрезки вида $A_{m} B_{m} \left ( 1\leq m\leq k \right )$, пересекающие $M$ более чем в одной точке. Обозначим через ${A}^{ \prime}_{m}$ вторую точку пересечения отрезка $ A_{m}B_{m}$ с контуром $M$. Тогда отрезки $A_{m}{A}^{ \prime}_{m}$ не пересекаются. Рассмотрим один из них и одну из частей $M$, на которые его делит $A_{m}{A}^{ \prime}_{m}$. Тогда в ней найдется такой отрезок $A_{p}{A}^{ \prime}_{p}$, что на части контура от $A_{p}$ до ${A}^{ \prime}_{p}$ нет других точек ${A}^{ \prime}_{q}$. Тогда там есть еще одна точка ${A}_{i}$, причем ${A}_{i}{B}_{i}$ не пересекает контур $M$. Аналогично, в другой части найдется точка ${A}_{j}$ такая, что отрезок ${A}_{j}{B}_{j}$ не пересекает контур $M$ рис.
Таким образом, отрезки ${A}_{i}{B}_{i}$ и ${A}_{j}{B}_{j}$ не пересекают отрезков ${A}_{p}{A}_{q}$ при $p,q \neq i$.
Применив предположение индукции к $\left ( n-1 \right )$ отрезку ${A}_{1}{B}_{1}$, ${A}_{2}{B}_{2}$, $\cdots$, ${A}_{i-1}{B}_{i-1}$, ${A}_{i+1}{B}_{i+1}$, …, ${A}_{n}{B}_{n}$, получаем, что точки ${A}_{1}$, ${A}_{2}$, $\cdots$, ${A}_{i-1}$, ${A}_{i+1}$, $\cdots$, ${A}_{n}$ можно соединить прыжками кузнечика. То же верно и в отношении точек ${A}_{1}$, ${A}_{2}$, …, ${A}_{j-1}$, ${A}_{j+1}$, $\cdots$, ${A}_{n}$. Наконец, и точки ${A}_{i}$ и ${A}_{j}$ также связаны прыжками кузнечика: из точки ${A}_{i}$ можно добраться до точки ${A}_{s}$, $s \neq I,j$, а из точки ${A}_{s}$ - до точки ${A}_{j}$.
