Разделы 
Дополнительно
Задача по математике - 3770
2019-06-16 
На столе стоят чашечные весы и $n$ гирь различных масс. Гири по очереди ставятся на чашки весов (на каждом шаге со стола берется любая гиря и добавляется на ту или другую чашку весов).
а) Докажите, что гири можно ставить в таком порядке, чтобы сначала перевесила левая чашка, затем правая, потом снова левая, снова правая и так далее.
Этой последовательности результатов взвешиваний сопоставим слово из букв $L$ и $R$: $LRLRLR \cdots$. Здесь буква $L$ обозначает, что перевесила левая чашка, а буква $R$ означает, что перевесила правая чашка.
б) Докажите, что для любого слова длины $n$ из букв $L$ и $R$ можно в таком порядке ставить гири на чашки весов, чтобы это слово соответствовало последовательности результатов взвешиваний.
Решение:
Пусть массы гирь $m_1 < m_2 < \cdots < m_n$.
а) Будем ставить гири так: на левую чашку $m_1$, затем на правую $m_2$, на левую $m_3$, на правую $m_4$ и т* д« При этом последовательность результатов взвешиваний будет такой: $LRLRLR \cdots$. Это вытекает из такого простого утверждения.
Лемма. Если $0 < m_1 < m_2 < \cdots < m_{k-1} < m_k$, то из двух сумм
$m_1 + m_3 + m_5 + \cdots$ и $m_2 + m_4 + m_6 + \cdots$
(содержащих все $n$ данных чисел) больше та, в которую попадает наибольшее число $m_k$.
Для ее доказательства надо при четном $k$ сложить неравенства $m_1 < m_2, m_3 < m_4, m_{k-1} < m_k$, а при нечетном $k - m_1 > 0 , m_3 > m_2, \cdots, m_k > m_{k-1}$.
Эта же лемма, но в применении к отрезку $m_i < m_{i+1} < \cdots < m_{k-1} < m_k$, состоящему из $k - l + 1$ чисел, пригодится
в решении задачи б).
б) Удобно описать порядок расстановки гирь, соответствующий данному слову из букв $L$ и $R$, «начиная с конца» слова.
Поставим все гири с четными номерами на одну чашку, с нечетными - на другую, причем самую тяжелую гирю $m_n$ поставим на левую или правую чашку в соответствии с последней буквой данного слова; затем, переходя от каждой буквы слова к предыдущей, будем снимать самую тяжелую из оставшихся гирь, если должна произойти смена буквы ($L$ на $R$ или $R$ на $L$), и самую легкую - если не должна. При этом каждый раз остается отрезок из (занумерованных подряд) гирь, которые, чередуясь, стоят на одной и другой чашке; к нему применима лемма.
На столе стоят чашечные весы и $n$ гирь различных масс. Гири по очереди ставятся на чашки весов (на каждом шаге со стола берется любая гиря и добавляется на ту или другую чашку весов).
а) Докажите, что гири можно ставить в таком порядке, чтобы сначала перевесила левая чашка, затем правая, потом снова левая, снова правая и так далее.
Этой последовательности результатов взвешиваний сопоставим слово из букв $L$ и $R$: $LRLRLR \cdots$. Здесь буква $L$ обозначает, что перевесила левая чашка, а буква $R$ означает, что перевесила правая чашка.
б) Докажите, что для любого слова длины $n$ из букв $L$ и $R$ можно в таком порядке ставить гири на чашки весов, чтобы это слово соответствовало последовательности результатов взвешиваний.
Решение:
Пусть массы гирь $m_1 < m_2 < \cdots < m_n$.
а) Будем ставить гири так: на левую чашку $m_1$, затем на правую $m_2$, на левую $m_3$, на правую $m_4$ и т* д« При этом последовательность результатов взвешиваний будет такой: $LRLRLR \cdots$. Это вытекает из такого простого утверждения.
Лемма. Если $0 < m_1 < m_2 < \cdots < m_{k-1} < m_k$, то из двух сумм
$m_1 + m_3 + m_5 + \cdots$ и $m_2 + m_4 + m_6 + \cdots$
(содержащих все $n$ данных чисел) больше та, в которую попадает наибольшее число $m_k$.
Для ее доказательства надо при четном $k$ сложить неравенства $m_1 < m_2, m_3 < m_4, m_{k-1} < m_k$, а при нечетном $k - m_1 > 0 , m_3 > m_2, \cdots, m_k > m_{k-1}$.
Эта же лемма, но в применении к отрезку $m_i < m_{i+1} < \cdots < m_{k-1} < m_k$, состоящему из $k - l + 1$ чисел, пригодится
в решении задачи б).
б) Удобно описать порядок расстановки гирь, соответствующий данному слову из букв $L$ и $R$, «начиная с конца» слова.
Поставим все гири с четными номерами на одну чашку, с нечетными - на другую, причем самую тяжелую гирю $m_n$ поставим на левую или правую чашку в соответствии с последней буквой данного слова; затем, переходя от каждой буквы слова к предыдущей, будем снимать самую тяжелую из оставшихся гирь, если должна произойти смена буквы ($L$ на $R$ или $R$ на $L$), и самую легкую - если не должна. При этом каждый раз остается отрезок из (занумерованных подряд) гирь, которые, чередуясь, стоят на одной и другой чашке; к нему применима лемма.
