Олимпиадная задача: Десять человек и орехи — инварианты и алгебраические методы

Решение 1:   Отберём у каждого из сидящих за столом по 10 орехов (у некоторых при этом число орехов может стать отрицательным). При этом из каждой “половины” (отдаваемой соседу и оставляемой у себя) вычтется по 5 орехов. Поэтому правило передачи орехов не нарушится. Теперь общее число орехов за столом равно нулю, и нам надо доказать, что через некоторое время у каждого из сидящих за столом будет по 0 орехов.   Занумеруем сидящих за столом по порядку числами от 1 до 10 так, что первый передает орехи второму, второй – третьему, ..., десятый – первому. Пусть уk-го человека в данный моментx_kорехов, а по сигналу он отдаёт соседуa_kи оставляет себеb_kорехов.   Рассмотрим сумму  S= |x₁| + |x₂| + ... + |x₁₀|.  Так как числаa_kиb_kодного знака(или хотя бы одно из них равно нулю), то  |x_k| = |a_k + b_k| = |a_k| + |b_k|,  то есть  S= |a₁| + |b₁| + ... + |a₁₀| + |b₁₀|.   После передачи орехов уk-го человека будет  a_k–1+b_k  орехов (если условиться, что  a₀=a₁₀).  Значение суммыSтеперь равно |a₁₀+b₁| + |a₁+b₂| + ... + |a₉+b₁₀| ≤ |a₁| + |b₁| + ... + |a₁₀| + |b₁₀|.   Таким образом,Sне увеличивается. Более того, неравенство становится строгим (Sуменьшается),если хотя бы для одного из значений kчислаa_k–1иb_kимеют разный знак(тогда  |a_k–1+b_k| < |a_k–1| + |b_k|).  В частности, это произойдёт при передаче орехов от человека с положительным числом орехов (будем обозначать его знаком "+"; ясно, что число орехов, которые онотдаёт соседу, также положительно) человеку с отрицательным ("–"; число орехов, которые оноставляет себе, также отрицательно). Если в какой-то момент за столом нет ни одной такой пары (но есть еще люди с ненулевым числом орехов), то найдётся группа вида  "+ 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).

Ответ задачи отсутствует