Задача 66824

Тема:    [ Индукция (прочее) ]

Сложность: 3 Классы: 8,9,10,11

Условие

Автор: Новиков В. В.

Любое число 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$.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
неизвестно
Дата	2019/20
Номер	41
вариант
Вариант	осенний тур, базовый вариант, 10-11 класс
задача
Номер	3