ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97807
Тема:    [ Полуинварианты ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Анджанс А.

Несколько ребят стоят по кругу. У каждого есть некоторое количество конфет. Сначала у каждого чётное количество конфет. По команде каждый передает половину своих конфет стоящему справа. Если после этого у кого-нибудь оказалось нечётное количество конфет, то ему извне добавляется одна конфета. Это повторяется много раз. Доказать, что настанет время, когда у всех будет поровну конфет.


Решение

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

Замечания

1. Задача предлагалась в "легком" варианте второго тура (7 баллов).

2. Задача предлагалась также на 49-й Ленинградской математической олимпиаде (1983, 9 кл., зад. 3).

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1982/1983
Номер 4
вариант
Вариант 9-10 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .