Западно-Китайская математическая олимпиада, 2015 год

На плоскости дано 100 прямых, и пусть $T$ — множество всех прямоугольных треугольников, ограниченных тремя прямыми. Найдите максимальное значение $|T|$, где $|T|$ означает количество элементов множества $T$.

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

Ответ: 62500.

Составим множества $A_1, A_2, ..., A_n$ следующим образом: каждая прямая принадлежит только одному из этих множеств, и две прямые параллельны, тогда и только тогда, когда они в одном множестве. Теперь построим множества $B_1, B_2, ..., B_n$ таким же образом как и множества $A_i$, только с условием, что прямые в множествах $B_i$ и $A_i$ перпендикулярны. Пусть $a_i$ количество прямых в множестве $A_i$, аналогично определим $b_i$. Тогда $\sum \limits_{i=1}^{n}{a_i}=\sum \limits_{i=1}^{n}{b_i}=100$. Так же получаем $2\cdot \left | T \right |= \sum \limits_{i=1}^{n}{a_ib_i(100-a_i-b_i)}$. Используя неравенство о средних, $a_ib_i \leq \frac{(a_i+b_i)^2}{4}$ $\Leftrightarrow a_ib_i(100-a_i-b_i)\leq \frac {(a_i+b_i)^2 \cdot (100-a_i-b_i)}{4} \leq \frac {50^2(a_i+b_i)}{4}$. Суммируя получим $2\cdot \left | T \right | \leq 125000$.

Пример: пусть в множествах $A_1, A_2, A_3, A_4$ по $25$ прямых. И прямые в множествах $A_1$ перпендикулярны прямым множества $A_2$, и прямые множества $A_3$ перпендикулярны прямым множества $A_4$.