СПбГУ 2022, отборочный этап, 10–11 классы, задача 12
( баллов) Петя задумал некоторое натуральное число. За один ход он может домножить его на любое рациональное число от до . Докажите, что за несколько таких операций Петя сможет получить число .
Ответ
Первое решение. Заметим, что любое рациональное число из интервала можно умножить на рациональное число из интервала , чтобы в итоге получилось число . Докажем, что произвольное положительное число домножениями на разрешенные числа можно поместить в этот интервал. Если мы имеем число, меньшее , то будем умножать его на . Рассмотрим первый момент, когда число стало больше или равно . Пусть до этого было число , а стало . Тогда . Следовательно, лежит в нужном интервале. Если изначально число было больше, чем , то аналогично будем умножать его на , пока оно не станет меньше .
Второе решение. Если в какой-то момент мы имеем число , то умножив его на , мы получим . А умножив его на , мы получим . Очевидно, что операциями увеличения или уменьшения на из любого натурального числа можно получить . Осталось только проверить, что мы умножаем на разрешенные числа. Действительно, и при выполнено .