Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, II тур заключительного этапа

Дано натуральное число $n.$ За одну операцию можно либо вычесть из имеющегося числа любое натуральное число, меньшее его наименьшего простого делителя, либо разделить его на его наименьший простой делитель. Существует ли такое составное $n,$ что из него нельзя получить простое число менее, чем за 2021 операцию? ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. Существует.
Решение. Пусть такого $n$ не существует. Тогда существует такое $m < 2021,$ что из каждого натурального числа можно указанными операциями получить простое не более чем за $m$ операций, и есть число $k,$ из которого нельзя получить простое число менее чем за $m$ операций. Будем получать простое число из числа $k!+k,$ следя отдельно за судьбой каждого из двух слагаемых. Всякий раз, когда мы вычитаем из суммы число, будем вычитать его из второго слагаемого, сохраняя первое, а на наименьший простой делитель суммы будем делить каждое из слагаемых. Поскольку второе слагаемое с каждой операцией убывает, перед каждой операцией текущее первое слагаемое будет делиться на текущее второе и все меньшие его числа, ибо можно считать, что предыдущими делениями были затронуты только сомножители в $k!,$ большие текущего второго слагаемого. Поэтому пока текущее второе слагаемое больше 1, наименьший простой делитель суммы не превосходит наименьшего простого делителя второго слагаемого и потому делит первое слагаемое — а, значит, и второе. Следовательно, наименьший простой делитель суммы равен наименьшему простому делителю второго слагаемого.
   Из сказанного следует, что пока текущее второе слагаемое больше 1, то, во-первых, оно при операциях ведет себя так, как будто первого слагаемого нет, и, во-вторых, текущая сумма является составным числом. Следовательно, не позднее момента, когда текущая сумма станет простым числом, текущее второе слагаемое должно обратиться в 1. Такое возможно только в случае, когда на предыдущем шаге второе слагаемое было простым числом. Но это значит, что к моменту превращения второго слагаемого в 1 — и, тем более, к моменту превращения суммы в простое число мы совершили не менее $k+1$ операции. Противоречие.

Опечатка в решении. В самом конце должно быть не $k+1,$ а $m+1$ операции.