Задача с AOPS"a

[nov]

Отрезок AB длины 1 разбит точками C1,C2,...,Cn на части AC1,C1C2,...,CnB. Эти части покрашены цветами A1,A2,...,Ak (k > 1) попеременно, в произвольном порядке (n > k-1, и можно считать, что точки Ci имеют любой цвет). Докажите , что для одного из этих цветов, для каждого 0 < d < 1/(k+1), найдутся 2 точки одного цвета на расстоянии d.

P.S. Задачки подобного типа мне очень нравятся, но тут даже при k=2 что-то не пошло...

[metelev]

Не знаю, интересно ли это ещё автору темы.

Например для $k=2$ можно попробовать использовать следующее рассуждение.

Возьмём какое-то $d$, соответствующее условию. Для $k=2$ получается $0<d<1/3$. Попробуем представить ситуацию, когда две точки, требуемые по условию, не найдутся.

Очевидно, если для какого-то из участков $C_i, C_{i+1}$ выполняется $|C_{i+1}-C_i|\geqslant d$, то внутри этого интервала найдутся две точки одного цвета на требуемом расстоянии. Поэтому рассмотрим случай, когда каждый участок отрезка $AB$ меньше $d$.

Построим дополнительный отрезок-"ползунок" длины $d$, который назовём $CD$. Совместим точку $C$ с точкой $A$, так чтобы точка $D$ оказалась между точками $A$ и $B$. Будем смещать отрезок $CD$ в направлении точки $B$. Допустим, изначально концы отрезка $CD$ попадают на участки разного цвета.

Следующее утверждение выглядит очевидным: до того, как точка $D$ отрезка $CD$ доползёт до точки $B$ по крайней мере один из концов отрезка $CD$ по крайней мере один раз пересечёт по крайней мере одну из точек $C_i$. Это следует из того, что $AC_1<d<1/3$. Таким образом, если изначально точки $C$ и $D$ попадали на участки разного цвета, то рано или поздно реализуется ситуация, когда они обе попадут на участки одного цвета.