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

Проект МЦНМО
при участии
школы 57
Задача 65864
Темы:    [ Теория алгоритмов (прочее) ]
[ Индукция (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 299 ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наименьшее количество ягод может оставить медвежатам лиса?


Решение

  Заметим, что на каждом шаге, если оба участвующих медвежонка имели хотя бы по ягоде, то у них по крайней мере по ягоде останется. Поэтому в конце у каждого медвежонка останется не меньше одной ягоды.
  Докажем, что лиса может оставить каждому медвежонку ровно по одной ягоде, то есть перейти из позиции  (1, 2, ..., 299)  в позицию  (1, 1, ..., 1).  Для этого докажем по индукции, что в случае n медвежат лиса из позиции  (1, 2, ..., 2n–1)  может перейти в позицию  (1, 1, ..., 1, 2n–1),  а из последней – в позицию  (1, 1, ..., 1).
  База. При  n = 1  все три позиции совпадают.
  Шаг индукции. Из позиции  (1, 2, ..., 2n–1, 2n),  забыв про последнего медвежонка, можно по предположению индукции перейти сначала в  (1, 1, ..., 1, 2n–1, 2n),  а потом в  (1, 1, ..., 1, 2n).  Задействовав последних двух медвежат, лиса переходит в позицию  (1, 1, ..., 1, 2n–1, 2n–1).  Теперь, снова забыв про последнего медвежонка, можно перейти в позицию  (1, 1, ..., 1, 2n–1),  а из неё, забыв про первого, – в позицию  (1, 1, ..., 1).


Ответ

100 ягод.

Замечания

5 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2016/17
Номер 38
вариант
Вариант осенний тур, базовый вариант, 8-9 класс
задача
Номер 5

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

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