https://avva.livejournal.com/3774286.html

Четвертая задача IMO-2025 на первый взгляд выглядит немного загадочно, но за абстрактным условием скрываются вполне конкретные ограничения, которые быстро приводят к решению. Вот условие:

Задача 4. Собственным делителем положительного целого числа N называется положительный делитель числа N, отличный от самого N. Бесконечная последовательность a1, a2, . . . состоит из положительных целых чисел, каждое из которых имеет по крайней мере три собственных делителя. Для каждого n ⩾ 1 число a_n+1 равно сумме трёх наибольших собственных делителей числа a_n. Определите все возможные значения числа a1.

Мое решение после спойлера:



Собственно, почему есть какие-то НЕ возможные значения a1? Потому что если в какой-то момент у очередного a_i нет трех собственных делителей (скажем, у простого числа есть только один - 1), то последовательность нельзя продолжить, а она должна быть бесконечная.

Пусть у очередного a_i есть не меньше трех собственных делителей, тогда можно описать их как деление a_i на a,b,c, где a < b < c. Например, три наибольших делителя 12 это 6,4,3, результат деления на a,b,c = 2,3,4. Будем обозначать число через (a,b,c) если его три наибольших собственных делителя это деление на a,b,c в этом порядке. Например, 12 это число вида (2,3,4), а 6 число вида (2,3,6).

Если у нас есть число a_i вида (a,b,c), то переход к a_i+1 это сумма a_i/a+a_i/b+a_i/c, т.е. по сути умножение a_i на (1/а+1/b+1/c). В зависимости от (a,b,c) число a_i может от этого уменьшиться, увеличиться, или остаться таким же. Поэтому все виды (a,b,c) делятся на три группы:
- увеличивающие: число a_i вида (a,b,c) увеличивается, переходя в a_i+1
- стабильные: число a_i вида (a,b,c) остается прежним, переходя в a_i+1
- уменьшающие: число a_i вида (a,b,c) уменьшается, переходя в a_i+1

Почти все (a,b,c) уменьшающие, потому что 1/a+1/b+1/c обычно меньше 1. Например, если a>2, т.е. исходное число a_i не делится на 2, то уже 1/3+1/4+1/5 меньше 1 (на самом деле (3,4,5) невозможно, т.е. число не может делиться на 4, не делясь на 2, но это педантизм). Если делится на 2, а на 3, не делится, то лучший вариант это (2,4,5) и 1/2+1/4+1/5 опять-таки меньше 1. Отсюда легко видно, что:

- увеличивающие тройки это только (2,3,4) и (2,3,5), и они умножают число на 13/12 и 31/30 соответственно;
- стабильная тройка это только (2,3,6): 1/2+1/3+1/6=1.
- все остальные тройки уменьшают число.

Мы видим, что числа типа 6*[что угодно без двоек и пятерок в множителях] это стабильное число: например, 6, 6*3, 6*7 итд. Оно не меняется и поэтому образует бесконечную последовательность: скажем, 18 -> 9+6+3 = 18. Такие числа точно все входят в ответ "возможные a_1".

С другой стороны, числа, которые увеличиваются, должны тоже делиться на 6, потому что они делятся на 2 и 3, но кроме того, у них есть еще минимум одна двойка (2,3,4) или если нет, то минимум одна пятерка (2,3,5). Когда такое число попадается в последовательности, результат его умножения на 13/12 или 31/30 соответственно убирает из его простых множителей одну шестерку (2*3) и эту дополнительную двойку либо пятерку (12=2*3*2, 30=2*3*5). После этого вполне может остаться число из стабильной группы, и тогда все хорошо; или опять число из увеличивающейся. А может получиться число
из уменьшающейся группы, не делящееся на 6.

Гипотеза: возможные значения для a_1 это либо стабильная группа, либо увеличивающаяся, которая через какое-то число шагов становится стабильной. Гипотеза: возможные значения для a_1 это либо стабильная группа, либо увеличивающаяся, которая через какое-то число шагов становится стабильной. Вместе их можно описать следующим образом: все числа, которые можно записать как 2^{2x+1}*3^y*t, где y>x и в t нет множителей 2,3,5. Или словами: нечетное число двоек, и число троек, большее, чем половина двоек, округленная вниз. Пятерок быть вообще не может (любая пятерка съест последнюю двойку, оставшуюся после того, как тройки съедят все парные по формуле (2,3,4) - ну или тройки закончатся, так или иначе, деление на 6 прекратится).

Чтобы доказать гипотезу, нужно доказать следующие два утверждения:

Во-первых, число не может все время увеличиваться на каждом шагу, рано или поздно оно либо стабилизируется, либо хотя бы раз уменьшится. Это очевидно из того, что умножение на 13/12 или 31/30 "съедает" минимум одну степень двойки у числа.

Во-вторых, если число на каком-то этапе уменьшается, оно уже никогда не станет стабильным или увеличивающимся. Чтобы доказать это, достаточно показать, что если a_i не делится на 6, то после перехода к a_i+1 тоже не делится. Если a_i не делится на 6, это может быть по двум причинам:

- a_i нечетное, тогда в тройке (a,b,c) все числа нечетные, и 1/a+1/b+1/c = (ab+bc+ac)/abc дробь, в которой и числитель, и знаменатель нечетные (в числителе сумма 3 нечетных чисел). Поэтому после умножения на эту дробь a_i+1 тоже нечетное.
- a_i четное, но не делится на 3, например его тройка (2,b,c), где b,c равны 1 или 2 по модулю 3. Можно рассмотреть, чему равно 2b+2c+bc по модулю 3, для всех четырех комбинаций b,c по модулю 3 (update: тут первоначально была ошибка, я написал, что для всех комбинаций 2b+2c+bc не делится на 3, но это не так, спасибо humanbean194 за проверку).

(1,1): 2*1+2*1+1*1 = 2 mod 3
(1,2): 2*1+2*2+1*2 = 2 mod 3
(2,1): тоже 2 mod 3, очевидно
(2,2): 0 mod 3, например (2,5,8): 40 -> 20+8+5 = 33, появляется тройка как множитель. (Но на самом деле (2,5,8) невозможно, потому что не может быть 8 без 4).

Покажем, что не может случиться число с частными (2,b,c) наибольших делителей, так, что b,c равны 2 по модулю 3, и после умножения на (1/2+1/b+1/c) число начинает делиться на 6. Если b,c оба нечетные, то число делится на 2, но не на 4 - иначе был бы такой делитель - а в дроби (2b+2c+bc)/2bc числитель нечетный, так что следующее число нечетное и не делится на 6. Пример: 110 -> 55+10+22. С другой стороны, если одно из них четное, это не может быть 4, потому что они оба 2 по модулю 3, и не может быть кратное 4, потому что тогда 4 появилось бы раньше. То есть мы в ситуации (2,*,2k), где k нечетное - 2k наибольшее число в тройке, потому что есть частные меньше его, например k. Более того, k должно быть простым, - если не простое, то поделив, найдем пару делителей больше. Скажем, (2,*,98) не может быть, хотя 98 равно 2 по модулю 3 и не делится на 4, потому что 98/2=49 не простое и мы можем поделить на 7 и 49 и 98 и получить (2,7,14) тройку меньше.

Выходит, третьим членом тройки обязано быть k, и наша тройка (2,k,2k) - им не может быть другое число m < 2k, кроме k, потому что тогда 2,k,m уже образуют тройку и 2k слишком большое. Но такая тройка невозможна, потому что k и 2k не могут оба быть 2 по модулю 3.

Итак, во всех случаях после перехода a_i->a_i+1 число не может начать делиться на 6, если до того не делилось, т.е. не может из разряда уменьшающихся перейти в стабильные или увеличивающиеся. Это доказывает гипотезу и заканчивает решение задачи.

https://avva.livejournal.com/3774286.html