Loading [MathJax]/jax/output/SVG/jax.js

Леонард Эйлер атындағы олимпиада, 2020-2021 оқу жылы, қорытынды кезеңнің 2-ші туры


Натурал n саны берілген. Бір операцияда жазылған санды сол санның ең кіші жай бөлгішінен кіші санға азайтса болады, немесе жазылған санды сол санның ең кіші жай бөлшегіне бөлуге болады. 2021-ден кем операция жасап жай сан алуға болмайтындай, құрама n саны табылады ма? ( С. Берлов )
посмотреть в олимпиаде

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

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

  1
4 года 1 месяца назад #

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