Разделы 
Дополнительно
Задача по математике - 3803
2019-06-16 
На прямой по порядку расположены точки $A_1, A_2, \cdots, A_n$ так, что длины отрезков $A_1A_2, A_2A_3, \cdots, A_{n-1}A_n$ не превосходят 1. Требуется отметить $k - 1$ из точек $A_2, \cdots, A_{n-1}$ красным цветом так, чтобы длины любых двух из $k$ частей, на которые отрезок $A_1A_n$ разбивается красными точками, отличались не более чем на 1. Докажите, что это всегда можно сделать:
а) для $k = 3$;
б) для каждого натурального $k < n - 1$.
Решение:
а) Рассмотрим возможные расстановки $T$ пары красных точек ($A_l, A_r$), делящих отрезок $A_0A_n$ на три части $A_0A_l, A_lA_r, A_rA_n$; наибольшую из длин этих частей обозначим $M$, наименьшую $m$. Из всех расстановок $T$ выберем такие, для которых $M$ минимальна, а из них - ту (или одну из тех), для которых $m$ максимальна. Докажем, что для такой расстановки $T = (A_l, A_r)$ будет выполнено условие $M - m \leq 1$.
Пусть для нее $M - m > 1$. Если ее части $M$ и $m$ расположены рядом, то, передвинув красную границу между ними на один отрезок, мы получим расстановку $T^{ \prime}$ у которой наименьшая часть больше $m$ и (возможно, или) наибольшая - меньше $M$, что противоречит выбору $T$. Если $m = A_0A_l, M = A_rA_n$, то либо у расстановки $(A_{i+1}A_r)$ наименьшая часть больше $m$, либо $A_{l+1}A_r \leq m < M - 1$ и тогда у расстановки $(A_{i+1}, A_{r+1})$ наибольшая часть меньше $M$: и то, и другое противоречит выбору $T = (A_i, A_r)$ (рис.).
б) Рассмотрим расстановку, у которой наибольшая по длине из $k$ частей $\Delta_1, \Delta_2, \cdots, \Delta_k$ равна $M$, а наименьшая равна $m < M - 1$. Пусть $\Delta_i = m$ лежит левее $\Delta_j = M$. Передвинем правый конец части $\Delta_i$ на один или несколько отрезков так, чтобы она стала не меньше $M - 1$ (но не больше $M$). Если теперь $\Delta_{i+1} < M - 1$, сделаем с ней то же самое, затем перейдем к $\Delta_{i+2}$ и т. д., пока либо длины всех частей $\Delta_i, \Delta_{i+1}, \cdots, \Delta_{j-1}$ не будут больше или равны $M-1$, либо нам удастся уменьшить $\Delta_j = M$ хотя бы на один отрезок. Затем (если в полученной расстановке по-прежнему $M - m > 1$) проделаем ту же процедуру еще несколько раз. При этом мы не можем повториться, поскольку вновь получаемая расстановка «лучше» в том смысле, что у нее либо строго меньше длина наибольшей части $M$, либо $M$ одинаковы, но меньше число частей, равных $M$, либо и это число одинаково, но тогда больше $m$ или (при равных $m$) меньше частей, равных $m$. Поскольку всего расстановок конечное число, после нескольких повторений процедуры мы придем к расстановке, которую «улучшить» невозможно, т. е. $М - m \leq 1$.
На прямой по порядку расположены точки $A_1, A_2, \cdots, A_n$ так, что длины отрезков $A_1A_2, A_2A_3, \cdots, A_{n-1}A_n$ не превосходят 1. Требуется отметить $k - 1$ из точек $A_2, \cdots, A_{n-1}$ красным цветом так, чтобы длины любых двух из $k$ частей, на которые отрезок $A_1A_n$ разбивается красными точками, отличались не более чем на 1. Докажите, что это всегда можно сделать:
а) для $k = 3$;
б) для каждого натурального $k < n - 1$.
Решение:
а) Рассмотрим возможные расстановки $T$ пары красных точек ($A_l, A_r$), делящих отрезок $A_0A_n$ на три части $A_0A_l, A_lA_r, A_rA_n$; наибольшую из длин этих частей обозначим $M$, наименьшую $m$. Из всех расстановок $T$ выберем такие, для которых $M$ минимальна, а из них - ту (или одну из тех), для которых $m$ максимальна. Докажем, что для такой расстановки $T = (A_l, A_r)$ будет выполнено условие $M - m \leq 1$.
Пусть для нее $M - m > 1$. Если ее части $M$ и $m$ расположены рядом, то, передвинув красную границу между ними на один отрезок, мы получим расстановку $T^{ \prime}$ у которой наименьшая часть больше $m$ и (возможно, или) наибольшая - меньше $M$, что противоречит выбору $T$. Если $m = A_0A_l, M = A_rA_n$, то либо у расстановки $(A_{i+1}A_r)$ наименьшая часть больше $m$, либо $A_{l+1}A_r \leq m < M - 1$ и тогда у расстановки $(A_{i+1}, A_{r+1})$ наибольшая часть меньше $M$: и то, и другое противоречит выбору $T = (A_i, A_r)$ (рис.).
б) Рассмотрим расстановку, у которой наибольшая по длине из $k$ частей $\Delta_1, \Delta_2, \cdots, \Delta_k$ равна $M$, а наименьшая равна $m < M - 1$. Пусть $\Delta_i = m$ лежит левее $\Delta_j = M$. Передвинем правый конец части $\Delta_i$ на один или несколько отрезков так, чтобы она стала не меньше $M - 1$ (но не больше $M$). Если теперь $\Delta_{i+1} < M - 1$, сделаем с ней то же самое, затем перейдем к $\Delta_{i+2}$ и т. д., пока либо длины всех частей $\Delta_i, \Delta_{i+1}, \cdots, \Delta_{j-1}$ не будут больше или равны $M-1$, либо нам удастся уменьшить $\Delta_j = M$ хотя бы на один отрезок. Затем (если в полученной расстановке по-прежнему $M - m > 1$) проделаем ту же процедуру еще несколько раз. При этом мы не можем повториться, поскольку вновь получаемая расстановка «лучше» в том смысле, что у нее либо строго меньше длина наибольшей части $M$, либо $M$ одинаковы, но меньше число частей, равных $M$, либо и это число одинаково, но тогда больше $m$ или (при равных $m$) меньше частей, равных $m$. Поскольку всего расстановок конечное число, после нескольких повторений процедуры мы придем к расстановке, которую «улучшить» невозможно, т. е. $М - m \leq 1$.
