19.18 Инварианты и полуинварианты

Отберём у каждого из сидящих за столом по 10 орехов (у некоторых при этом число орехов может стать отрицательным). При этом из каждой “половины” (отдаваемой соседу и оставляемой у себя) вычтется по 5 орехов. Поэтому правило передачи орехов не нарушится. Теперь общее число орехов за столом равно нулю, и нам надо доказать, что через некоторое время у каждого из сидящих за столом будет по 0 орехов.

Занумеруем сидящих за столом по порядку числами от 1 до 10 так, что первый передает орехи второму, второй – третьему, , десятый — первому. Пусть у -го человека в данный момент орехов, а по сигналу он отдаёт соседу и оставляет себе орехов.

Рассмотрим сумму . Так как числа и одного знака (или хотя бы одно из них равно нулю), то то есть

После передачи орехов у -го человека будет орехов (если условиться, что ). Значение суммы теперь равно

Таким образом, не увеличивается. Более того, неравенство становится строгим ( уменьшается), если хотя бы для одного из значений числа и имеют разный знак (тогда ). В частности, это произойдёт при передаче орехов от человека с положительным числом орехов (будем обозначать его знаком «»; ясно, что число орехов, которые он отдаёт соседу, также положительно) человеку с отрицательным («»; число орехов, которые он оставляет себе, также отрицательно). Если в какой-то момент за столом нет ни одной такой пары (но есть еще люди с ненулевым числом орехов), то найдётся группа вида «» (по правую руку от «» сидят несколько человек с нулевым числом орехов, а затем «»). Заметим, что число нулей между «» и «» при каждом ходе уменьшается (левый 0 превращается в «», а остальные 0 и «» не меняются). Поэтому через несколько ходов «» и «» окажутся рядом и сумма уменьшится.

Таким образом, сумма не может “остановиться” ни на каком положительном значении. А так как эта сумма — целое неотрицательное число, то когда-нибудь она станет равной нулю, то есть у всех станет по 0 орехов.