Разделы 
Дополнительно
Задача по математике - 1104
2015-03-10 
Найдите наибольшее число областей, на которые рассекают круг отрезки, соединяющие $n$ точек, лежащих на его окружности.
Решение:
Пусть отрезки, соединяющие $n$ точек, разбивают круг на $u_{n}$ областей и $z_{n}$ — множество всех этих отрезков. Условимся нумеровать точки по ходу движения часовой стрелки: $A_{1}, \cdots, A_{n},$ и добавим еще одну точку $A_{n+1}$ между $A_{n}$ и $A_{1}$. При проведении отрезка $A_{n+1}A_{k} (k=1, \cdots, n)$ рассечется надвое столько областей, на сколько частей отрезки множества $z_{n}$ рассекают сам отрезок $A_{n+1}A_{k}$. Отрезок $A_{n+1}A_{k}$ пересекают отрезки, соединяющие любую из точек $A_{1}, \cdots , A_{k-1}$ с любой из точек $A_{k+1}, \cdots, A_{n}$ (но не пересекает внутри отрезки, исходящие из $A_{n+1}$ или $A_{k}$). Таких отрезков ровно $(k-1)(n-k)$, а точек деления столько же или меньше; последнее случится тогда, когда некоторые из точек деления совпадут. Число частей на единицу больше числа точек деления. Таким образом, при проведении отрезка $A_{n+1}A_{k}$ число областей увеличивается не более чем на $1 + (k-1)(n-k)$. Эта оценка не зависит от того, проведены или еще нет другие отрезки из $A_{n+1}$. Всего, после проведения всех отрезков $A_{n+1}A_{1}, \cdots, A_{n+1}A_{n}$, число областей будет не более
$u_{n} + \sum_{k=1}^{n} (1+(k-1)(n-k)) = u_{n} + n +n \cdot \sum_{k=1}^{n} (k-1) - \sum_{k=1}^{n}k(k-1)$.
Нетрудно доказать по индукции следующую формулу:
$\sum_{k=1}^{n} (k-1) \cdots (k-s) = \frac{1}{s+1} \cdot n(n-1) \cdots (n-s)$.
Тогда после преобразований получим:
$u_{n+1} \leq u_{n} + n + \frac{n(n-1)(n-2)}{6}$.
Суммируя все эти неравенства и учитывая, что $u_{1} = 1$, получаем:
$u_{n} \leq 1 + \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)(n-3)}{24}$.
Если в конфигурации $z_{n}$ никакие три отрезка не пересекаются в одной точке, то все подсчитанные нами точки деления различны, и неравенство превращается в равенство:
$Max u_{n} = 1 + \frac{n(n+1)}{2} + \frac{n(n-1)(n-2)(n-3)}{24}$.
Остается проверить, что такую конфигурацию можно осуществить. Докажем это по индукции.
Пусть точки $A_{1}, \cdots , A_{n}$ уже выбраны указанным образом. Соединим прямыми каждую точку пересечения отрезков $z_{n}$ со всеми вершинами $A_{1}, \cdots ,A_{n}$. Занумеруем вторые точки пересечения этих прямых с окружностью буквами $ B_{1}, \cdots, B_{m}$. Их число $m$ конечно и не превосходит $n [c^{2}]^{2}$ (его можно выразить через $u_{n}$, но этого не требуется). Очевидно, если выбрать за $A_{n+1}$ любую точку окружности, отличную от $B_{1}, \cdots, B_{m}$, то отрезки $A_{n+1}A_{k}$ не будут проходить через точки пересечения отрезков $z_{n}$, что и означает, что в конфигурации $z_{n+1}$ также никакие три отрезка не пересекаются в одной точке.
Найдите наибольшее число областей, на которые рассекают круг отрезки, соединяющие $n$ точек, лежащих на его окружности.
Решение:
Пусть отрезки, соединяющие $n$ точек, разбивают круг на $u_{n}$ областей и $z_{n}$ — множество всех этих отрезков. Условимся нумеровать точки по ходу движения часовой стрелки: $A_{1}, \cdots, A_{n},$ и добавим еще одну точку $A_{n+1}$ между $A_{n}$ и $A_{1}$. При проведении отрезка $A_{n+1}A_{k} (k=1, \cdots, n)$ рассечется надвое столько областей, на сколько частей отрезки множества $z_{n}$ рассекают сам отрезок $A_{n+1}A_{k}$. Отрезок $A_{n+1}A_{k}$ пересекают отрезки, соединяющие любую из точек $A_{1}, \cdots , A_{k-1}$ с любой из точек $A_{k+1}, \cdots, A_{n}$ (но не пересекает внутри отрезки, исходящие из $A_{n+1}$ или $A_{k}$). Таких отрезков ровно $(k-1)(n-k)$, а точек деления столько же или меньше; последнее случится тогда, когда некоторые из точек деления совпадут. Число частей на единицу больше числа точек деления. Таким образом, при проведении отрезка $A_{n+1}A_{k}$ число областей увеличивается не более чем на $1 + (k-1)(n-k)$. Эта оценка не зависит от того, проведены или еще нет другие отрезки из $A_{n+1}$. Всего, после проведения всех отрезков $A_{n+1}A_{1}, \cdots, A_{n+1}A_{n}$, число областей будет не более
$u_{n} + \sum_{k=1}^{n} (1+(k-1)(n-k)) = u_{n} + n +n \cdot \sum_{k=1}^{n} (k-1) - \sum_{k=1}^{n}k(k-1)$.
Нетрудно доказать по индукции следующую формулу:
$\sum_{k=1}^{n} (k-1) \cdots (k-s) = \frac{1}{s+1} \cdot n(n-1) \cdots (n-s)$.
Тогда после преобразований получим:
$u_{n+1} \leq u_{n} + n + \frac{n(n-1)(n-2)}{6}$.
Суммируя все эти неравенства и учитывая, что $u_{1} = 1$, получаем:
$u_{n} \leq 1 + \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)(n-3)}{24}$.
Если в конфигурации $z_{n}$ никакие три отрезка не пересекаются в одной точке, то все подсчитанные нами точки деления различны, и неравенство превращается в равенство:
$Max u_{n} = 1 + \frac{n(n+1)}{2} + \frac{n(n-1)(n-2)(n-3)}{24}$.
Остается проверить, что такую конфигурацию можно осуществить. Докажем это по индукции.
Пусть точки $A_{1}, \cdots , A_{n}$ уже выбраны указанным образом. Соединим прямыми каждую точку пересечения отрезков $z_{n}$ со всеми вершинами $A_{1}, \cdots ,A_{n}$. Занумеруем вторые точки пересечения этих прямых с окружностью буквами $ B_{1}, \cdots, B_{m}$. Их число $m$ конечно и не превосходит $n [c^{2}]^{2}$ (его можно выразить через $u_{n}$, но этого не требуется). Очевидно, если выбрать за $A_{n+1}$ любую точку окружности, отличную от $B_{1}, \cdots, B_{m}$, то отрезки $A_{n+1}A_{k}$ не будут проходить через точки пересечения отрезков $z_{n}$, что и означает, что в конфигурации $z_{n+1}$ также никакие три отрезка не пересекаются в одной точке.
