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