Олимпиада начальной школы 2x2, 5 класс, 2017 год, 1 тур
дата проведения: 29 января 2017
Задача 10.
Лёша записал на доске натуральное число, меньшее 1000. Каждую секунду он делит текущее число на доске на 2, если оно чётное и записывает результат деления вместо предыдущего числа. Если же число на доске нечётно, он прибавляет к нему 1 и тоже записывает результат сложения вместо прежнего числа. Через какое наибольшее число ходов у Лёши может впервые получиться число 1 на доске?
Например, если было записано 5, то мы получаем 1 через 5 ходов:
5 ⟶ 6 ⟶ 3 ⟶ 4 ⟶ 2 ⟶ 1
Ответ на Задачу 10.
Ответ: Через 19 ходов.
Идея решения: Решим задачу с конца:
1 - 2 - 4 - 3 - 6 - 5 - 10 - 9 - 18 - 17 - 34 - 33 - 66 - 65 - 130 - 129 - 258 - 257 - 514 - 513.
Очевидно, что это самая длинная возможная цепочка ходов. Значит, не позже чем через 19 ходов он получит 1.
