Задача
Несколько ребят стоят по кругу. У каждого есть некоторое количество конфет. Сначала у каждого чётное количество конфет. По команде каждый передает половину своих конфет стоящему справа. Если после этого у кого-нибудь оказалось нечётное количество конфет, то ему извне добавляется одна конфета. Это повторяется много раз. Доказать, что настанет время, когда у всех будет поровну конфет.
Решение
Пусть 2m – наибольшее, а 2n – наименьшее количество конфет у одного человека. После одного круга обмена и, возможно, добавления конфет извне, m не увеличится, а количество людей, имеющих 2n конфет, уменьшится. (Действительно, каждый человек оставляет себе не более m конфет, а получает не более m + 1 конфеты. Причём, если он получил m + 1 конфету, то одна из них была добавлена извне, значит, после получения m конфет у него стало не более 2m – 1 конфеты. С другой стороны, если m > n, среди людей имевших 2n конфет, найдётся человек, который получит более n конфет.) Значит, через несколько шагов n увеличится. Так как n увеличивается, а m не увеличивается, наступит момент, когда n станет равным m.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь