ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .