Один из очень действенных способов решения задач — это метод математической индукции. Когда нам нужно доказать некоторое утверждение для n значений, причем n либо не определено либо достаточно большое мы можем эффективно использовать этот метод. Суть метода довольно проста. Мы проверяем утверждение для минимального n, зачастую n=1 (База индукции). Затем предполагаем, что утверждение верно для n=k, важно понимать, что мы не доказываем предположение (Предположение индукции). И наконец доказываем, что утверждение верно для n=k+1, при доказательстве мы должны либо свести этот случай к предыдущему (n=k) либо наоборот показать, как от предыдущего перейти к этому (Шаг индукции). Доказав шаг индукции мы доказываем, что утверждение верно для любых n.
Условие:
Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше — 2 ягоды, следующий — 4 ягоды, и так далее, самому старшему досталось 2 в степени 99 ягод. Лиса предложила им поделить ягоды «по справедливости». Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наименьшее количество ягод может оставить медвежатам лиса?
Идея:
Оценить минимальное количество оставшихся ягод и показать как его получить.
Решение:
Очевидно, что меньше 100 ягод остаться у медвежат не может. Покажем как лиса может оставить медвежатам ровно 100 ягод.
Заметим, что имея n медвежат с 1 ягодой и одного медвежонка с 2 в степени n ягодами, можно получить n+1 медвежонка с n+1 ягодой. Докажем с помощью математической индукции.
1) База индукции. Пусть n=1. То есть у нас один медвежонок с 1 ягодой и один с двумя. Делим поровну (остается одна лишняя ягода, которую съедает лиса) и остается два медвежонка по одной ягоде.
2) Предположение индукции. Пусть для n=k выполняется.
3) Шаг индукции. Теперь докажем для n=k+1. Берем медвежонка с 2 в степени k+1 ягодой и одного из медвежат с одной ягодой. Делим поровну и получаем два медвежонка с 2 в степени k ягод и k медвежат с одной ягодой. По предположению индукции мы можем сначала из одного медвежонка с 2 в степени k ягод и к медвежат с 1 ягодой получить k+1 медвежонка с 1 ягодой, а затем аналогично взять второго медвежонка с 2 в степени k ягод и k (из k+1) медвежат с 1 ягодой и получить k+1 медвежонка с 1 ягодой. Итого получим k+2 медвежонка с 1 ягодой.
Таким образом при помощи метода математической индукции мы показали, как получить 100 медвежат с одной ягодой.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!