Республиканская олимпиада по математике, 2005 год, 10 класс

На окружности радиуса 1 отмечены $n$ точек. Докажите, что существует не более $\dfrac{n^2}{3}$ различных отрезков, длины которых больше $\sqrt2$, с концами в этих точках.

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

Пусть имеется точка $x$ проведём через неё диаметр и перпендикулярный диаметр (будет его называть «$l$»).

Разделим окружность двумя диаметрами на четыре равные части, пусть слева направо начиная с верхней части будут расположены эти $n$ точек $x_{1}, x_{2}, x_{3}, ... x_{n}$ .

Из условия требуется найти то максимальное количество точек (для каждого $x_{1},x_{2},...x_{n}$ ) которые будут располагаться за $l$ так как нужно найти отрезки которые больше $\sqrt{2}=\sqrt{1^2+1^2}$ и разделить на $2$ это и будет максимальное количество нужных отрезков.

Рассмотрим три случая

1) Пусть точки будут располагаться на окружности по разные стороны от диаметра , если в одной части будут таких $a$ количество точек, то на второй $n-a$ тогда в сумме $a(n-a)$ рассмотрев как функцию $f(a)=an-a^2$ откуда при $a=[\dfrac{n}{2}]$ достигается максимум $f_max=[\dfrac{n^2}{4}]$ откуда $\frac{n^2}{4}<\dfrac{n^2}{3}$ или в случае нечётного $\dfrac{n^2-1}{4}<\dfrac{n^2}{3}$

для $n>0$.

2) Пусть точки оказались в четырёх равных частях на которые он был поделён, положим количество точек сверху по часовой на каждой четвертях фиксировано равны $a,b,c,d$ и пусть они располагаются так чтобы $(b,c,d)$ и $(a,c,d)$ лежали за $l$ относительно $a$ и $b$ соответсвенно, тогда $c,d$ лежат в одной плоскости в $l$ относительно друг друга, докажем что максимум для этих количеств точек будет лежат именно в таком расположений.

Выпишем количество точек которые потенциальное будут удовлетворят условию задачи (лежат за $l$ для каждой точки из $a,b,c,d$) для одной из $a$ это сумма $b+c+d$ значит общее количество $a(b+c+d)$ так же для остальных $b(a+c+d), c(a+b+c), d(a+b+c)$ пусть в сумме все четыре слагаемых дадут $s$ тогда нужное количество отрезов равна $s-2cd$ при условий $a \geq b \geq c \geq d$ тогда докажем что при выше описанном расположений точек на окружности, построение достигнет максимума, для этого требуется доказать что при других расположений общая сумма точек лежащих «в $l$» для каждой точки будет больше $2cd$, пусть некоторое количество точек в $d$ не лежит «в $l$» относительно точек в части $c$ тогда он лежит в $a$, пусть это под часть равна $y$ тогда общее количество точек лежащих в $l$ относительно $c,d$ как минимум $2c(d-y)+2ya=2(cd-cy+ay) \geq 2cd $ или $a>c$ что верно так учитывая вышеописанное условие, аналогично для других секторов.

Значит задача сводится к максимизации функций $s-2cd= 2(ab+ac+ad+bc+bd)$ или сразу поделив найдём количество точек которые больше $\sqrt{2}$ то есть $f_{max}=ab+ac+ad+bc+bd$ при условий $a+b+c+d=n$

Преобразуя $f=a(b+c+d)+b(c+d)=a(n-a)+b(n-a-b)$ тогда $a=\dfrac{\pm \sqrt{-3b^2+2bn+n^2-4f}-b+n}{2}$

или $ f \leq \dfrac{-3b^2+2bn+n^2}{4}$ но при $b=\dfrac{n}{3}$ правая часть достигает максимума, значит при $a=b=\dfrac{n}{3}$ значение $f_{max}=\dfrac{n^2}{3}$ и $c+d=\dfrac{n}{3}$

3) когда какие то точки лежат только на трёх частях окружности, здесь ответ так же $f_{max}=\dfrac{n^2}{3}$ так как в предыдущей части $c+d=\dfrac{n}{3}$.