Конкурсная задача ММ53 (8 баллов)

Найти самое маленькое число, допускающее представление в виде суммы шести слагаемых, обладающее следующими свойствами:
1) каждое слагаемое является натуральным числом;
2) любые два слагаемых не взаимно просты;
3) любые три слагаемых взаимно просты;
4) сумма любых четырех слагаемых кратна 4;
5) сумма любых пяти слагаемых кратна 5.

Решение задачи ММ53

Решение

Для выполнения условий 4 и 5 необходимо и достаточно, чтобы все шесть слагаемых лежали в одном и том же классе вычетов по модулю 20. Шесть слагаемых образуют 15 сочетаний по два. Каждая такая пара должна иметь НОД, взаимно простой с НОД других пар. Минимально возможными подходящими НОД являются числа 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59. 2 и 5 пропущены, поскольку слагаемые, содержащие их в качестве сомножителей, не могут быть сравнимы с остальными по модулю 20.
Пусть a, b, c, d, e, f, g, h, i, j, k, l, m, n, o - вышеперечисленные 15 простых чисел, взятые в некотором порядке. Тогда шесть слагаемых, удовлетворяющих условиям 1-3 будут выглядеть так:
abcde,
afghi,
bfjkl,
cgjmn,
dhkmo,
eilno.
Наша задача - распределить значения так, чтобы все произведения лежали в одном классе вычетов по модулю 20 и при этом сумма получившихся чисел была наименьшей (для этого слагаемые должны быть как можно ближе друг к другу, и значит, к корню шестой степени из их произведения). Квадрат произведения выбранных 15 чисел сравним с 9 по модулю 20. Это означает, что все шесть искомых слагаемых должны лежать в одном из следующих четырех классов: 3, 7, 13, 17 (значения корня 6-й степени из 9 по модулю 20).
Следующие шесть чисел:
6109697 = 11⋅19⋅23⋅31⋅41;
5675097 = 3⋅29⋅37⋅41⋅43;
4849977 = 3⋅11⋅47⋅53⋅59;
7156877 = 7⋅13⋅31⋅43⋅59;
5367257 = 7⋅17⋅23⋅37⋅53;
5723237 = 13⋅17⋅19⋅29⋅47
очевидно удовлетворяют всем пяти пунктам задачи.

Остается доказать, что их сумма, s = 34882142, является наименьшим числом, допускающим требуемое разложение. Во-первых, заметим, что замена хотя бы одного из выбранных 15 простых чисел ведет к увеличению s. В самом деле, в измененный набор должно входить хотя бы одно простое число, большее 59, но уже замена 59 на 61 приводит к тому, что кубический корень из произведения чисел модифицированного набора становится больше найденного s.

Значительно труднее показать минимальность s для слагаемых, составленных из чисел нашего набора. Я делал это компьютерным перебором, отталкиваясь из сравнимости всех произведений с 3 (7, 13, 17) по модулю 20. Перебор получается довольно большим, но его легко сокращать, заранее отбрасывая бесперспективные ветви. Однако каждое такое сокращение усложняет алгоритм перебора. Поэтому я не стал добиваться слишком уж большой оптимизации, а остановился на первом же варианте, просчитываемом за приемлемое время.

Обсуждение

Возможен и менее переборный, но гораздо более трудоемкий в рассуждениях вариант поиска и обоснования оптимальности s. В моем распоряжении имеются (весьма громоздкие) выкладки Олега Полубасова, реализующие такой подход. Олег рассматривает полный взвешенный граф, в котором вершинами являются искомые слагаемые, а ребрами - НОД соответствующих вершин, и ищет оптимум методом ветвей и границ.
Насколько можно судить по скупому описанию Влада Франка, его подход аналогичен подходу Олега. Но Влад не стал заниматься оптимизацией вручную, а произвел компьютерный перебор.

Само собой, задача 53 допускает ряд обобщений и аналогов. По этому поводу см. задачи MM56 и ММ208.

Награды

За решение этой задачи Влад Франк получает 8 призовых баллов. Виктор Филимоненков, которому (при правильных рассуждениях) не удалось найти минимальное число, получает 4 призовых балла. Наиболее полное исследование прислал Олег Полубасов. Олег заявил, что выступает вне конкурса. Поэтому мне ничего не остается, кроме как оценить его решение в 10 внеконкурсных призовых баллов ;)

Эстетическая оценка задачи - 3.3 балла

---