На прямой по порядку расположены точки $A_0$, $A_1$, $A_2$, $\ldots$, $A_n$ так, что длины отрезков $A_0A_1$, $A_1A_2$, $\ldots$, $A_{n-1}A_n$ не превосходят 1. Требуется отметить $k-1$ из точек $A_1$, $A_2$, $\ldots$, $A_{n-1}$ красным цветом так, чтобы длины любых двух из $k$ частей, на которые отрезок $A_0A_n$ разбивается красными точками, отличались не более, чем на 1. Докажите, это всегда можно сделать:
для $k=3$,
для каждого натурального $k\lt n$.
В. Гринберг, В. М. Гальперин
Всесоюзная математическая олимпиада школьников (1979 год, 10 класс)
Сначала сформулируем условие задачи несколько иначе. Будем рассматривать всевозможные расстановки $k+1$ фишек $M_0$, $M_1$, $M_2$, $\ldots$, $M_k$ в точках $A_0$, $A_1$, $\ldots$, $A_n$. Расстановку назовём правильной, если $M_i$ расположена не правее, чем $M_{i+1}$, и расстояния между $M_i$ и $M_{i+1}$ различаются не более, чем на 1 ($0\le i \lt k$). Тогда исходная задача превратится в такую: доказать, что существует правильная расстановка фишек $M_0$, $M_1$, $\ldots$, $M_k$ такая, что $M_0$ находится в $A_0$, а $M_k$ — в $A_n$. Может, конечно, оказаться, что в этой расстановке $M_i$ и $M_j$ попали в одну точку, но тогда, очевидно, $|A_0A_n|\lt k-1$ (подумайте сами, что надо делать в этом случае).
Покажем, как из произвольной правильной расстановки фишек получить другую правильную, в которой часть фишек сдвинется вправо, а $M_0$ останется на месте. Введём предварительно некоторые обозначения.
Пусть мы имеем расстановку фишек $M_0$, $M_1$, $\ldots$, $M_k$. Будем через $M_i$ обозначать также ту точку $A_j$, в которой находится фишка $M_i$, а через $M_i'$ — точку $A_{j+1}$ (если она существует — см. рисунок). В частности, $|M_iM_i'|\lt1$. Мы покажем, как часть фишек переставить с $M_i$ на $M_i'$ с сохранением правильности расстановки.
Выберем среди расстояний $|M_iM_{i+1}|$ минимальное; пусть это $|M_sM_{s+1}|=a$. Тогда $a\le|M_iM_{i+1}|\le a+1$ при всех $i$ (так как расстановка правильная). Если нам удастся передвинуть часть фишек вправо с сохранением этих неравенств, то новая расстановка будет правильной. Посмотрим, нет ли среди фишек $M_1$, $M_2$, $\ldots$, $M_k$ такой фишки $M_i$, для которой $|M_{i-1}M_i'|\le a+1$, т. е. такой, при сдвиге которой вправо все новые расстояния между фишками не превысят $a+1$. Все такие фишки назовём левоподвижными. Оказывается, левоподвижные фишки существуют. Действительно, такова, например, фишка $M_{s+1}$: $$
|M_sM_{s+1}'|=|M_sM_{s+1}|+|M_{s+1}M_{s+1}'|=a+|M_sM_{s+1}'|\le a+1.
$$
Теперь посмотрим, нет ли среди фишек $M_0$, $M_1$, $\ldots$, $M_{k-1}$ такой, для которой $|M_i'M_{i+1}|\ge a$, т. е. такой, при сдвиге которой вправо ни одно из расстояний между фишками не станет меньше $a$. Такие фишки назовём правоподвижными. Правоподвижной, естественно, будет и фишка $M_k$.
Заметим, что если $M_i$ не является левоподвижной, то $|M_{i-1}M_i'|\gt a$. В самом деле,
$$
|M_{i-1}'M_i'|=|M_{i-1}M_i'|-|M_{i-1}M_{i-1}'|\gt(a+1)-|M_{i-1}M_{i-1}'|\ge(a+1)-1=a.
$$
А если фишка $M_i$ не является правоподвижной, то $$
|M_i'M_{i+1}'|=|M_i'M_{i+1}|+|M_{i+1}M_{i+1}'|\le a+1.
$$
Теперь из всех левоподвижных фишек выберем самую правую. Пусть это будет $M_l$. Среди всех правоподвижных фишек из $M_l$, $M_{l+1}$, $\ldots$, $M_k$, выберем самую левую. Пусть это будет $M_r$ (возможно, $l=r$). Теперь сдвинем фишки $M_l$, $M_{l+1}$, $\ldots$, $M_r$ в положения $M_l'$, $M_{l+1}'$, $\ldots$, $M_r'$ соответственно и покажем, что последовательность $M_0$, $\ldots$, $M_k$ останется правильной.
$$
|M_{l-1}M_l'|\gt|M_{l-1}M_l|\ge a\quad\text{и}\quad|M_{l-1}M_l'|\le a+1,
$$
так как фишка $M_r$ — левоподвижная.
$$
|M_r'M_{r+1}|\lt|M_rM_{r+1}|\le a+1\quad\text{и}\quad|M_r'M_{r+1}|\ge a,
$$
так как фишка $M_r$ — правоподвижная.
При $l\le i\lt r$, согласно сделанным выше замечаниям относительно свойств неподвижных фишек, $a\lt|M_i'M_{i+1}'|\le a+1$, так как фишка $M_{i+1}$ — нe левоподвижная (она стоит правее $M_l$ — самой правой левоподвижной фишки), а $M_i$ — не правоподвижная (она стоит левее $M_r$ — самой левой правоподвижной фишки). Поэтому для всех расстояний $|M_{i-1}M_i|$ остаётся верным неравенство $a\le|M_{i-1}M_i|\le a+1$, $i=1$, 2, $\ldots$, $k$. Надо, правда, ещё доказать, что фишка $M_i$ не может оказаться правее фишки $M_{l+1}$, но это понятно, так как если раньше было $M_i=M_{i+1}$, то фишка $M_{i+1}$ — левоподвижная и, значит, фишка $M_i$ двигаться не могла. Итак, мы добились следующего: из любой правильной последовательности сдвигом некоторой части фишек $M_1$, $M_2$, $\ldots$, $M_k$ на соседние точки ($M_i$ сдвигалось в $M_i'$) вправо получена новая правильная последовательность.
Отметим интересную роль, которую сыграли в этом процессе фишки $M_s$ и $M_k$. Они сами в операции, быть может, нe участвовали, но их наличие обеспечило существование необходимых нам фишек $M_l$ и $M_r$.
Теперь завершить доказательство совсем просто. Поместим все фишки $M_0$, $\ldots$, $M_k$ в $A_0$)— эта последовательность, очевидно, правильная — и начнём применять процесс.
Расстановка фишек по точкам всё время меняется, причём каждая фишка движется лишь вправо. Ясно, что после некоторого количества таких операций фишка $M_k$ придёт в точкy $A_n$, что и требовалось.
Другие известные решения задачи используют такую процедуру (говоря в терминах приведённого выше решения): сначала фишки $M_0$ и $M_k$ закрепляют в точках $A_0$ и $A_n$ соответственно, а остальные расставляют произвольно; затем передвижением фишек $M_1$, $M_2$, $\ldots$, $M_{k-1}$ добиваются требуемого. (Этот подход сразу кажется наиболее естественным, поэтому так неожиданна идея изложенного решения: не закреплять фишку $M_k$.)
