СПбГУ 2024, 8-9 классы, задача 4
( баллов) Возьмем произвольное натуральное число . Вычислим значение и уберем из его разложения на простые множители все множители, кроме двоек и троек. Полученное число назовем . Например,
Потом вычислим значение и уберем из этого числа все простые множители, кроме двоек и троек, полученное число назовем и т. д. Докажите, что с какого бы натурального числа мы ни начали, через некоторое время в этой последовательности встретится число .
Решение. Допустим, что нашлось некоторое , для которого последовательность не содержит . Тогда все числа в последовательности, начиная со второго, могут иметь в разложении на множители только простые множители и . Далее в рассуждениях считаем, что . Заметим, что если делится на простое число , то , очевидно, не делится на и, следовательно, не делится на . Отсюда следует, что в последовательности чередуются степени и . Проверим, что последовательность убывает и из-за этого в ней все-таки должна содержаться .
Экспериментируя с , видим, что в этих случаях последовательность быстро приходит к . Поэтому можно считать, что чередующиеся степени имеют показатели не меньше .
Пусть (где ), . Тогда или , или получается из числа сокращением на какие-то простые множители не меньшие (потому что это число не делится на ). В первом случае - это степень двойки, на которую делится число
т. е. , что не соответствует нашим ограничениям - слишком маленький показатель. Во втором случае .
Теперь рассмотрим случай , (где , ). Здесь аналогично или , или получается из числа сокращением на какие-то простые множители, не меньшие . Второй случай опять ведет к убыванию, что нам и требуется. В первом случае - это степень тройки, на которую делится число
т. е. , что не соответствует нашим ограничениям.
Замечание. Для и первый случай можно рассмотреть несколько иначе. А именно, тогда
Правая часть делится на только при четных , пусть , мы можем считать, что . Тогда разложим правую часть на множители
Поскольку нечетные множители в правой части взаимно просты (так как их разность равна ) и больше , равенство было бы возможно только в случае когда одна из скобок равна , а другая равна , но разность этих чисел равна только при . Значит, первый случай при наших ограничениях невозможен.