Европейская математическая олимпиада среди девочек (EGMO). 2021 год. Грузия

Жазықтықта $O$ нүктесi белгiленген, оны бас нүкте деп атайық. Осы жазықтықта келесi шарттарды қанағаттандыратын 2021 нүктеден тұратын $P$ жиынын қарастырайық
   (i) $P$-ның ешқандай үш нүктесi бiр түзудiң бойында жатпайды және
   (ii) $P$-ның екi нүктесiн қосатын ешқандай түзу бас нүкте арқылы өтпейдi.
   Егер $O$ нүктесi $P$-ның үш нүктесi құрайтын үшбұрыштың iшiнде (қатаң түрде) жатса, ондай үшбұрышты толық үшбұрыш деп атайық. Жазықтықта ең көп дегенде қанша үшбұрыш толық болуы мүмкiн?

Комментарий/решение

Пусть $n = 2021$. Общее количество треугольников, которые можно составить из точек множества $P$, равно

\[\binom{n}{3}.\]

Обозначим количество толстых треугольников через $N_{\text{thick}}$, а количество треугольников, не содержащих точку $O$ (тонких), через $N_{\text{thin}}$. Тогда

\[N_{\text{thick}} = \binom{n}{3} - N_{\text{thin}}.\]

Следовательно, для максимизации $N_{\text{thick}}$ необходимо минимизировать $N_{\text{thin}}$.

Пронумеруем точки $P_1, P_2, \dots, P_n$ в порядке обхода против часовой стрелки вокруг точки $O$.

Для каждой точки $P_i$ проведём прямую $L_i$, проходящую через точки $P_i$ и $O$.

В силу условия (ii), ни одна другая точка множества $P$ не лежит на этой прямой.

Пусть $k_i$ — количество точек множества $P$, лежащих в открытой полуплоскости относительно прямой $L_i$ в направлении обхода против часовой стрелки.

Треугольник $P_iP_jP_m$ является тонким тогда и только тогда, когда все три его вершины лежат в некоторой открытой полуплоскости, граница которой проходит через точку $O$.

Количество таких треугольников можно посчитать, зафиксировав их «первую» вершину в порядке обхода:

\[N_{\text{thin}} = \sum_{i=1}^{n} \binom{k_i}{2}.\]

2. Минимизация суммы.

Заметим, что для любой пары точек $(P_i, P_j)$ точка $P_j$ либо находится в «своей» полуплоскости для $P_i$, либо наоборот.

Следовательно, сумма всех $k_i$ является константой:

\[\sum_{i=1}^{n} k_i = \frac{n(n-1)}{2}.\]

Сумма

\[\sum_{i=1}^{n} \binom{k_i}{2}\]

минимизируется, когда значения $k_i$ распределены максимально равномерно.

Так как $n = 2021$ — нечётное число, мы можем добиться того, чтобы для всех $i$ выполнялось

\[k_i = \frac{n-1}{2}.\]

\[k_i = \frac{n - 1}{2} = \frac{2020}{2} = 1010.\]

Такая конфигурация реализуется, например, если точки $P$ являются вершинами правильного $n$-угольника с центром $O$.

Минимальное количество тонких треугольников:

\[N_{\text{thin}}^{\min}= n \cdot \binom{\frac{n-1}{2}}{2}= n \cdot \frac{\frac{n-1}{2}\left(\frac{n-1}{2}-1\right)}{2}= \frac{n(n-1)(n-3)}{8}.\]

Максимальное количество толстых треугольников:

\[N_{\text{thick}}^{\max}= \binom{n}{3} - \frac{n(n-1)(n-3)}{8}= \frac{n(n-1)(n-2)}{6} - \frac{3n(n-1)(n-3)}{24}.\]

Приводя к общему знаменателю:

\[N_{\text{thick}}^{\max}= \frac{n(n-1)}{24}\left[4(n-2) - 3(n-3)\right]= \frac{n(n-1)(n+1)}{24}= \frac{n(n^2 - 1)}{24}.\]

Для $n = 2021$:

\[N = \frac{2021(2021^2 - 1)}{24}= \frac{2021 \cdot 2020 \cdot 2022}{24}.\]

\[N = 2021 \cdot 505 \cdot 337 = 343\,943\,885.\]

Ответ: $343\,943\,885$. Тривиальная идея.