Задача 7.
На каждом шаге к данному числу можно прибавить единицу или удвоить его. За какое наименьшее число шагов из числа 1 можно получить число 51?
Ответ на Задачу 7.
Ответ: 8.
Решение:
Пример получения за 8 шагов: 1 − 2 − 3 − 6 − 12 − 24 − 25 − 50 − 51. Покажем, что за 7 шагов этого сделать невозможно. Для получения числа 51 последним шагом может быть только 50 − 51, а первый шаг не зависит от выбора операции. Предположим, что из 2 получили 50 за 5 шагов. Среди этих шагов должна присутствовать первая операция. Иначе за пять 6 шагов получим число 2 = 64 . Заметим, что если к числу n применяется сначала первая операция, а затем вторая, то получим число 2n + 2. Если наоборот, то 2n + 1. Кроме того, в первом случае получается число большее, чем во втором: 2n + 2 > 2n + 1. Значит, даже если первая операция только одна и выполняется первой, за пять шагов получим: 2 − 3 − 6 − 12 − 24 − 48, число 48 меньше, чем 50.
