Конкурсная задача ММ264 (4 балла)
Назовем пару натуральных чисел a и b аддитивной, если τ(a+b)=τ(a)+τ(b),σ(a+b)=σ(a)+σ(b) и φ(a+b)=φ(a)+φ(b).
Доказать, что существует бесконечно много аддитивных пар.
(τ(n), σ(n), φ(n) - количество натуральных делителей, сумма натуральных делителей и функция Эйлера соответственно.)
Решение
Привожу решения Олега Полубасова и Мераба Левиашвили.
Обсуждение
Рекордно низкая эстетическая оценка ММ264 могла бы быть значительно выше. Самые низкие оценки сопровождались приписками, что они могут быть существенно повышены, если будет предъявлен способ конструирования аддитивных пар, не основанный на переборе. Впрочем, сами строгие оценщики не верили в существование такого решения.
Не верил в решение, не основанное на переборе, и ведущий. Но надеялся, что конкурсанты предложат хотя и переборный, но высоко эффективный способ конструирования примитивных (не получаемых из других домножением на одно число) аддитивных пар. Примерно такой, какой был предложен для http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_163. (Обладатели моей книжки про Марафон могут найти в ней обобщение способа, изложенного в ММ163.)
Отчасти эти надежды оправдались. Мераб Левиашвили предложил способ поиска аддитивных пар, в которых числа a, b и a+b имеют фиксированное каноническое разложение. После того как были назначены конкретные значения двум из шести простым числам, фигурирующим в решении, остальные были найдены конечным и совсем коротким ручным перебором.
Такой подход был бы хорош, если бы не одно «но». Я не уверен, что другие назначения, отличные от c=2? e=3, приведут к нахождению еще хотя бы одной аддитивной пары. Так что, успех на пути, выбранном Мерабом, выглядит, скорее случайным, чем закономерным. (Еще одна претензия к решению Мераба связана с загадочной формулой в третьей строке второй страницы его решения.)
Не исключено, что можно получать аддитивные пары (а точнее тройки), стартуя с других канонических разложений a, b и a+b. Однако, среди примитивных наборов найденных Олегом Полубасовым (а он нашел больше всего таких наборов), вид канонического разложения всех трех чисел (a, b и a+b) не повторяется ни разу. Так что, способ конструирования серий примитивных наборов пока не вырисовывается.
Награды
За решение задачи ММ264 участники Марафона получают следующие призовые баллы:
Мераб Левиашвили - 5;
Олег Полубасов - 5;
Анатолий Казмерчук - 4;
Денис Овчинников - 4;
Василий Дзюбенко - 4;
Владислав Франк - 4;
Александр Романов - 4;
Константин Шамсутдинов - 3;
Виктор Филимоненков - 2;
Владимир Дорофеев - 2.
Эстетическая оценка задачи - 3.1 балла