Разделы 
Дополнительно
Задача по математике - 1031
2015-02-14 
В плоскости даны $n>4$ точек, причем никакие три не лежат на одной прямой. Покажите, что можно найти не менее $C_{n-3}^{2}$ выпуклых четырехугольников с вершинами в четырех данных точках.
Решение:
Некоторые участники олимпиады дали лучшую оценку, чем требовалось условием задачи. Они показали, что число выпуклых четырехугольников с вершинами в данных $n$ точках не меньше, чем $\frac{C_{n}^{5}}{n-4}$. За такое решение жюри присудило специальные призы. Мы приводим одно из этих решений.
Лемма. Среди 5 точек на плоскости, никакие три из которых не лежат на одной прямой, найдутся 4, образующие выпуклый четырехугольник.
Доказательство леммы найдите сами.
Рассмотрим все возможные группы по 5 точек, выбранные из данных $n$ точек (они существуют, так как $n>4$). Таких групп будет $C_{n}^{4}$. В каждой группе найдется по крайней мере одна четверка точек, образующих выпуклый четырехугольник. Но каждый такой четырехугольник мог быть сосчитан $n-4$ раза, так как при фиксированных четырех точках — вершинах этого четырехугольника — в качестве пятой точки можно взять любую из оставшихся $n-4$ точек. Поэтому всего выпуклых четырехугольников будет не менее $\frac{C_{n}^{5}}{n-4}$. Покажем, что $\frac{C_{n}^{5}}{n-4} \geq C_{n-3}^{2}$. Эквивалентными преобразованиями получим:
$\frac{n(n-1)(n-2)(n-3)(n-4)}{120(n-4)} \geq \frac{(n-3)(n-4)}{2}$;
$n(n-1)(n-2) -60(n-4) \geq 0; n^{3} – 3n^{2} – 58n+240 \geq 0$.
Полученный многочлен имеет три корня: $n=5; n=6; n=-8$. Неравенство можно переписать в виде $(n-5)(n-6)(n+8) \geq 0$. Так как $n>4$, то равенство имеет место только при $n=5$ и $n=6$.
При $n>6$ имеет место строгое неравенство $\frac{C_{n}^{5}}{n-4} > C_{n-3}^{2}$.
В плоскости даны $n>4$ точек, причем никакие три не лежат на одной прямой. Покажите, что можно найти не менее $C_{n-3}^{2}$ выпуклых четырехугольников с вершинами в четырех данных точках.
Решение:
Некоторые участники олимпиады дали лучшую оценку, чем требовалось условием задачи. Они показали, что число выпуклых четырехугольников с вершинами в данных $n$ точках не меньше, чем $\frac{C_{n}^{5}}{n-4}$. За такое решение жюри присудило специальные призы. Мы приводим одно из этих решений.
Лемма. Среди 5 точек на плоскости, никакие три из которых не лежат на одной прямой, найдутся 4, образующие выпуклый четырехугольник.
Доказательство леммы найдите сами.
Рассмотрим все возможные группы по 5 точек, выбранные из данных $n$ точек (они существуют, так как $n>4$). Таких групп будет $C_{n}^{4}$. В каждой группе найдется по крайней мере одна четверка точек, образующих выпуклый четырехугольник. Но каждый такой четырехугольник мог быть сосчитан $n-4$ раза, так как при фиксированных четырех точках — вершинах этого четырехугольника — в качестве пятой точки можно взять любую из оставшихся $n-4$ точек. Поэтому всего выпуклых четырехугольников будет не менее $\frac{C_{n}^{5}}{n-4}$. Покажем, что $\frac{C_{n}^{5}}{n-4} \geq C_{n-3}^{2}$. Эквивалентными преобразованиями получим:
$\frac{n(n-1)(n-2)(n-3)(n-4)}{120(n-4)} \geq \frac{(n-3)(n-4)}{2}$;
$n(n-1)(n-2) -60(n-4) \geq 0; n^{3} – 3n^{2} – 58n+240 \geq 0$.
Полученный многочлен имеет три корня: $n=5; n=6; n=-8$. Неравенство можно переписать в виде $(n-5)(n-6)(n+8) \geq 0$. Так как $n>4$, то равенство имеет место только при $n=5$ и $n=6$.
При $n>6$ имеет место строгое неравенство $\frac{C_{n}^{5}}{n-4} > C_{n-3}^{2}$.
