|
|
 |
Условие
За круглым столом сидят десять человек, перед каждым – несколько орехов. Всего орехов – сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка – если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.
Решение 1
Отберём у каждого из сидящих за столом по 10 орехов (у некоторых при этом число орехов может стать отрицательным). При этом из каждой “половины” (отдаваемой соседу и оставляемой у себя) вычтется по 5 орехов. Поэтому правило передачи орехов не нарушится. Теперь общее число орехов за столом равно нулю, и нам надо доказать, что через некоторое время у каждого из сидящих за столом будет по 0 орехов.
Занумеруем сидящих за столом по порядку числами от 1 до 10 так, что первый передает орехи второму, второй – третьему, ..., десятый – первому. Пусть у k-го человека в данный момент xk орехов, а по сигналу он отдаёт соседу ak и оставляет себе bk орехов.Рассмотрим сумму S = |x1| + |x2| + ... + |x10|. Так как числа ak и bk одного знака (или хотя бы одно из них равно нулю), то |xk| = |ak + bk| = |ak| + |bk|, то есть S = |a1| + |b1| + ... + |a10| + |b10|.
После передачи орехов у k-го человека будет ak–1 + bk орехов (если условиться, что a0 = a10). Значение суммы S теперь равно
|a10 + b1| + |a1 + b2| + ... + |a9 + b10| ≤ |a1| + |b1| + ... + |a10| + |b10|.
Таким образом, S не увеличивается. Более того, неравенство становится строгим (S уменьшается), если хотя бы для одного из значений k числа ak–1 и bk имеют разный знак (тогда |ak–1 + bk| < |ak–1| + |bk|). В частности, это произойдёт при передаче орехов от человека с положительным числом орехов (будем обозначать его знаком "+"; ясно, что число орехов, которые он отдаёт соседу, также положительно) человеку с отрицательным ("–"; число орехов, которые он оставляет себе, также отрицательно). Если в какой-то момент за столом нет ни одной такой пары (но есть еще люди с ненулевым числом орехов), то найдётся группа вида "+ 0 ... 0 –" (по правую руку от "+" сидят несколько человек с нулевым числом орехов, а затем "–"). Заметим, что число нулей между "+" и "–" при каждом ходе уменьшается (левый 0 превращается в "+", а остальные 0 и "–" не меняются). Поэтому через несколько ходов "+" и "–" окажутся рядом и сумма S уменьшится.
Таким образом, сумма S не может “остановиться” ни на каком положительном значении. А так как эта сумма – целое неотрицательное число, то когда-нибудь она станет равной нулю, то есть у всех станет по 0 орехов.
Решение 2
Пусть M – максимальное число орехов, находящихся в данный момент у одного человека. Достаточно доказать, что когда-нибудь M станет равным 10. Очевидно, M не может увеличиться. Пусть M > 10. Покажем, что тогда через некоторое время M уменьшится. Назовем людей, имеющих M орехов, богатыми; имеющих M – 1 орех, зажиточными; а остальных – бедными. За столом обязательно есть бедные люди (иначе общее число орехов было бы больше 100). Мы докажем, что количество богачей (при данном M) постепенно уменьшается. Как только оно станет равным 0, уменьшится M (и появятся новые богачи). Разберём два случая.
1) M чётно: M = 2n. Заметим, что если человек в данный момент не богат, то по сигналу он оставляет себе не больше n – 1, а получает от соседа не больше n орехов. Таким образом, он никогда не будет иметь M орехов, то есть новых богачей не возникает.
Рассмотрим группу подряд сидящих людей, самый правый из которых богат, самый левый – беден, а остальные (если они есть) – зажиточные. (Такая группа всегда найдётся. Действительно, попросим выйти из-за стола всех зажиточных. Очевидно, теперь есть место, где богатый сидит по правую руку от бедного.) Если длина этой группы больше 2, то на каждом ходу она уменьшается на 1: самый левый зажиточный становится бедным (он отдаёт n орехов, а получает не более n – 1), а остальные зажиточные и богач “сохраняют свой статус”. В конце концов длина группы станет равна 2, и на следующем ходу богач из этой группы станет зажиточным.
2) M нечётно. Заметим, что операцию в условии задачи можно разбить на два этапа: сначала каждый передаёт "меньшую половину" своих орехов налево, а затем каждый передаёт всю свою кучку направо. Второй этап, очевидно, не влияет на число орехов в кучках, и его можно отбросить. При этом все проблемы, связанные с чётностью, меняются на противоположные (в частности, теперь богачи не могут возникать при нечётном M), то есть
п. 2) после такого изменения эквивалентен уже доказанному п. 1).
Замечания
8 баллов
