На отрезке $[0;1]$ по очереди отмечаются точки $x_0$, $x_1$, $x_2$, $\ldots$, $x_n$. Для каждой точки $x_k$ ($k=1$, $\ldots$, $n$) измеряется расстояние $d_k$ от неё до ближайшей к ней из поставленных ранее точек. Докажите, что $$d_1+d_2+\dots+d_n \le 1+\dfrac{\log_2 n}2.
$$
Покажем сначала, что любой набор точек $x_0$, $x_1$, $\ldots$, $x_n$ на отрезке $[0;1]$ можно, не уменьшая суммы $$s=d_1+d_2+\ldots+d_n,$$ преобразовать в набор, две первые точки которого — 0 и 1, а каждая следующая — середина одного из отрезков, на которые предыдущие точки разбивают$[0;1]$. Ясно, что можно ограничиться наборами различных точек (если точка $x_i$ совпала с одной из предыдущих, её можно просто вычеркнуть — $d_i=0$ — и добавить новую точку в конце). Но нам будет удобно допустить совпадения.
Рис. 1Рис. 2. Преобразование набора $x_0$, $x_1$, $\ldots$, $x_n$ при сдвиге точки $x_2$: каждому значению $x_2$, $0\le x_2\le1$, отвечает горизонтальный отрезок, на пересечении которого с синими линиями расположены точки $x_i$.Рис. 3
Пусть $x_i$ — самая левая, $x_k$ — самая правая точка набора. Очевидно, $s$ не уменьшится, если заменить $x_i$ на 0, а $x_k$ — на 1. Кроме того, при $i\ge1$ можно поменять $x_i$ и $x_{i-1}$ друг с другом местами — при этом сумма $d_{i-1}+d_i$ может только возрасти (рис. 1), а остальные слагаемые суммы $s$ не изменятся. Поэтому впредь можно считать, что $x_0=0$, а $x_1=1$. Будем «улучшать» набор $x_0$, $\ldots$, $x_n$ дальше. Рассмотрим точку $x_2$. Если $x_2=x_0$ или $x_2=x_1$, пропустим её и перейдём к $x_3$. Пусть теперь $x_2=x$, $0\lt x\lt1$. Будем двигать точку $x_2=x$ по отрезку $[0;1]$ и при этом один из отрезков $[0;x]$ или $[x;1]$ вместе со всеми попавшими на него точками $x_i$ растягивать, а другой — сжимать (рис. 2). Ясно, что тогда сумма чисел $d_i$ для точек $x_i$ отрезка $[0;x]$ будет изменяться пропорционально $x$, а для отрезка $[x;1]$ — пропорционально $1-x$, поэтому общая сумма, как функция $x$, будет равна
$$s=1+\min(x,1-x)+lx+r(1-x)$$
($d_1=1$, $d_2=\min(x,1-x)$, $l$ и $r$ — постоянные). Эта функция линейна на отрезках $\left[0;\dfrac12\right]$ и $\left[\dfrac12;1\right]$ и имеет излом в точке $x=\dfrac12$ (рис. 3), поэтому её максимум достигается в одной из точек 0, $\dfrac12$, 1. Сдвинем $x_2$ в точку максимума и одновременно соответствующим образом растянем (или сожмём) набор точек $x_i$ на отрезках $[0;x_2]$ и $[x_2;1]$. Мы получим набор точек, у которого сумма $s$ не меньше первоначальной, а точка $x_2$ находится либо в середине отрезка $[x_0;x_1]$ $\left(x_2=\dfrac12\right)$, либо на краю этого отрезка. Если, далее, $x_3$ не совпадает ни с одной из точек $x_0$, $x_1$, $x_2$, рассмотрим тот из отрезков $[x_0;x_2]$ и $[x_2;x_1]$, на котором лежит $x_3$. Как и выше, мы можем так изменить набор точек $x_i$ на этом отрезке, чтобы точка $x_3$ стала его серединой или концом, и при этом сумма $s$ не уменьшилась. Поступая так же со следующими точками, мы придём к набору, в котором $x_0=0$, $x_1=1$, а каждая следующая точка совпадает либо с серединой отрезка, соединяющего две соседние ранее поставленные точки, либо с одной из этих точек. Все точки, совпадающие с предыдущими, можно вычеркнуть, после чего останется набор из $k$ точек ($k\le n$), удовлетворяющий сформулированному в начале решении условию.
Для такого набора точек $d_1=1$, $d_2=\dfrac12$, $d_3=\dfrac14$, $d_4=\dfrac14$ или $\dfrac18$ при $i\ge2$ каждое число $d_i$ равно $2^{-m}$ с некоторым натуральным $m$, причём чисел, равных $2^{-m}$, имеется не более $2^{m-1}$. Ясно, что наибольшее значение сумма первых $n$ таких чисел принимает при $$
d_1=1,\quad d_2=\dfrac12,\quad d_3=d_4=\dfrac14,\quad d_5=\ldots=\dfrac18,\quad\ldots\tag1
$$
($d_i=2^{-m}$ при $2^{m-1}\lt i\le2^m$), т. е. для последовательности точек
$$
0,~~1,~~\dfrac12,~~\dfrac14,~~\dfrac34,~~\dfrac38,~~\dfrac58,~~\dfrac78,~~\dfrac1{16},~~{\ldots}\tag2
$$
(дроби с одинаковыми знаменателями в этой последовательности можно переставлять). Остаётся оценить сумму $s(n)=d_1+\ldots+d_n$ для последовательности (1). При $n=2^m+k$, $0\le k\lt2^m$, $m\ge0$
$$
s(n)=1+\dfrac12+2\cdot\dfrac14+4\cdot\dfrac18+\ldots+2^{m-1}\cdot\dfrac1{2^m}+\dfrac k{2^{m+1}}=1+\dfrac m2+\dfrac k{2^{m+1}},
$$
т. е. $s(n)=1+\dfrac12\log_2n$ при $n=2^m$, а на участках от $2^m$ до $2^{m+1}$ функция $s(n)$ меняется линейно. Поскольку $\log_2x$ — выпуклая функция, $s(n)\le1+\dfrac12\log_2n$ при всех натуральных $n$ (рис. 4).
Рис. 4. Красные точки — значения $s(n)$.
Интересно, что оптимальное расположение точек (2) даётся «жадным» алгоритмом (это вполне официальный термин): на каждом шагу достаточно обеспечивать максимум очередного слагаемого, не заботясь о дальнейшем.
