|
||||||||||||||||||
|
СодержаниеММ53Конкурсная задача ММ53 (8 баллов)
Найти самое маленькое число, допускающее представление в виде суммы шести слагаемых, обладающее следующими свойствами: Решение
Для выполнения условий 4 и 5 необходимо и достаточно, чтобы все шесть слагаемых лежали в одном и том же классе вычетов по модулю 20.
Шесть слагаемых образуют 15 сочетаний по два. Каждая такая пара должна иметь НОД, взаимно простой с НОД других пар. Минимально возможными подходящими НОД являются числа 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59. 2 и 5 пропущены, поскольку слагаемые, содержащие их в качестве сомножителей, не могут быть сравнимы с остальными по модулю 20. Остается доказать, что их сумма, s = 34882142, является наименьшим числом, допускающим требуемое разложение. Во-первых, заметим, что замена хотя бы одного из выбранных 15 простых чисел ведет к увеличению s. В самом деле, в измененный набор должно входить хотя бы одно простое число, большее 59, но уже замена 59 на 61 приводит к тому, что кубический корень из произведения чисел модифицированного набора становится больше найденного s. Значительно труднее показать минимальность s для слагаемых, составленных из чисел нашего набора. Я делал это компьютерным перебором, отталкиваясь из сравнимости всех произведений с 3 (7, 13, 17) по модулю 20. Перебор получается довольно большим, но его легко сокращать, заранее отбрасывая бесперспективные ветви. Однако каждое такое сокращение усложняет алгоритм перебора. Поэтому я не стал добиваться слишком уж большой оптимизации, а остановился на первом же варианте, просчитываемом за приемлемое время. Обсуждение
Возможен и менее переборный, но гораздо более трудоемкий в рассуждениях вариант поиска и обоснования оптимальности s. В моем распоряжении имеются (весьма громоздкие) выкладки Олега Полубасова, реализующие такой подход. Олег рассматривает полный взвешенный граф, в котором вершинами являются искомые слагаемые, а ребрами - НОД соответствующих вершин, и ищет оптимум методом ветвей и границ. Само собой, задача 53 допускает ряд обобщений и аналогов. По этому поводу см. задачи MM56 и ММ208. Награды За решение этой задачи Влад Франк получает 8 призовых баллов. Виктор Филимоненков, которому (при правильных рассуждениях) не удалось найти минимальное число, получает 4 призовых балла. Наиболее полное исследование прислал Олег Полубасов. Олег заявил, что выступает вне конкурса. Поэтому мне ничего не остается, кроме как оценить его решение в 10 внеконкурсных призовых баллов ;) Эстетическая оценка задачи - 3.3 балла
|
|||||||||||||||||
|
||||||||||||||||||
|