|
|
 |
Условие
Сто медвежат нашли в лесу ягоды: самый младший успел схватить 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 баллов
