Задача 66824
|
|
 |
Условие
Любое число $x$, написанное на доске, разрешается заменить либо на 3$x$ + 1, либо на [x/2].
Докажите, что если вначале написано число 1, то такими операциями можно получить любое натуральное число.
Решение
Число 1 написано. Покажем, как получить натуральное $n$ > 1, если мы уже умеем получать все меньшие числа. Число $n$ представимо в одном из трёх видов: 3$k$ – 1, 3$k$ или 3$k$ + 1, где $k$ натуральное.
1) $2k – 1 \to 6k – 2 \to 3k – 1$;
2) $2k \to 6k + 1 \to 3k$;
3) $k \to 3k + 1$.
Замечания
4 балла
