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

Решение

Для выполнения условий 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 будут выглядеть так:
a*b*c*d*e,
a*f*g*h*i,
b*f*j*k*l,
c*g*j*m*n,
d*h*k*m*o,
e*i*l*n*o.
Наша задача - распределить значения так, чтобы все произведения лежали в одном классе вычетов по модулю 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 допускаает ряд обобщений и аналогов. По этому поводу см. задачу 56.

Награды

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

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