Тема 19. Задачи на теорию чисел

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела задачи на теорию чисел

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#34788Максимум баллов за задание: 4

За круглым столом сидят десять человек, перед каждым — несколько орехов. Всего орехов — сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка, если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.

Показать ответ и решение

Отберём у каждого из сидящих за столом по 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 орехов.

Ответ: Доказательство