Конкурсная задача ММ268 (9 баллов)
Назовем натуральное число m допустимым, если существует такое n, что из чисел 1,2,…,n можно составить сумму произведений, в которой каждое число встречается ровно один раз, равную m. Сколько существует недопустимых чисел?
Примечание: в суммах произведений допускаются одиночные слагаемые. Например, число 148 допустимо, поскольку 148=1·3 + 2·5·8 + 4 + 6·9 + 7.
Решение
Привожу решения Виктора Филимоненкова (для поклонников сестры таланта), Анатолия Казмерчука и Мераба Левиашвили.
Обсуждение
К устаканившемуся составу конкурсантов присоединился еще один участник. Точнее, это они к нему присоединились: Михаил Ватник прислал свое решение ММ268 сразу после обнародования задач XXVII конкурса.
Больших затруднений задача не вызвала (вопреки тому, что казалась мне непростой).
Мне понравился ответ к этой задаче. Набор 4, 8, 13 на первый взгляд кажется случайным. И лишь при погружении в задачу становится ясно, что это уменьшенные на 2 треугольные числа.
Влад Франк отметил и обосновал интуитивно очевидный факт: для подходящих достаточно больших чисел количество представлений может быть сколь угодно большим.
Анатолий Казмерчук и Мераб Левиашвили напротив сосредоточили внимание на числах, допускающих малое количество представлений. При этом представления, отличающиеся лишь порядком слагаемых, разумеется, не различались. А вот представления, полученные переброской сомножителя 1 в другое слагаемое, Анатолий считал различными. А Мераб рассмотрел обе возможные трактовки. При этом Мераб рассмотрел не только числа, имеющие единственное представление, но и допускающие по два, по три… представления. Правда, как ему удалось обнаружить второе представление для числа 12, для меня осталось загадкой
Награды
За решение задачи ММ268 участники Марафона получают следующие призовые баллы:
Мераб Левиашвили - 12;
Анатолий Казмерчук - 11;
Владислав Франк - 10;
Василий Дзюбенко - 9;
Денис Овчинников - 9;
Александр Романов - 9;
Константин Шамсутдинов - 9;
Виктор Филимоненков - 9;
Олег Полубасов - 9;
Владимир Дорофеев - 9;
Михаил Ватник - 9.
Эстетическая оценка задачи - 4 балла