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

Сколько элементов содержит множество сумм квадратов цифр квадратов чисел, в десятичной записи которых присутствуют по одному разу ровно три ненулевых цифры: 1, 4, 9? (Нулей может быть сколько угодно).

Решение

Привожу решения Виктора Филимоненкова, Дениса Овчинникова и Анны Букиной.

Обсуждение

ММ258 не вызвала затруднений ни у кого из тех, кто прислал решения. Интересно, что в большинстве присланных решений перебор минимизирован настолько, что его вполне можно осуществить вручную.

Естественные обобщения задачи рассмотрели Олег Полубасов и Анатолий Казмерчук. Процитирую Олега:

«Если рассмотреть всевозможные тройки {a, b, c} от {1, 1, 1} до {9, 9, 9}, то окажется, что размеры множеств сумм могут принимать следующие значения: 2-38, 40, 42-49, 52, 56, 57, 60. Двухэлементное множество сумм даёт тройка {1, 1, 1}, а 60-элементное – тройка {7, 8, 9}. Чаще всего (13 раз) встречается размер 24. Размер 25 встречается 7 раз.»

Эта техническая и достаточно рутинная задача возникла как побочный продукт из попытки решить более содержательную задачу.
Легко понять, что суммы квадратов цифр натурального числа может быть любым натуральным числом (достаточно ограничиться рассмотрением репьюнитов).
Немногим сложнее обосновывается, что сумма цифр квадрата натурального числа может быть любым натуральным числом, сравнимым с 0, 1, 4, 7 (квадратами) по модулю 9.
А вот с суммами квадратов цифр квадратов натуральных чисел дело обстоит интереснее. По-видимому, они могут принимать любые значения за исключением 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 20.
При попытке обосновать это утверждение и возникла данная задача. Почему именно 1, 4, 9?
Во-первых, сумма число 149 приводит 13, а 1049 - к 19 (эти числа наряду с 15, 17 и 18 входят в список небольших чисел, имеющих нетривиальные требуемые представления). А во-вторых, 1, 4, 9 (фигурирующие в условии) - это все ненулевые цифры, являющиеся квадратами, а 25 (фигурирующее в ответе) тоже квадрат. Мне показалось, что это будет уместно в задаче про сумму квадратов цифр квадратов чисел.

Сама же попытка обоснования приведенного предположения утонула в переборе переборов и к задаче не привела.

Награды

За решение задачи ММ258 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 8
Олег Полубасов - 8
Владислав Франк - 8
Константин Шамсутдинов - 7
Денис Овчинников - 7
Виктор Филимоненков - 7
Анна Букина - 7.

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

---

PS: Владислав Франк прислал мне строгое доказательство того, что каждое натуральное число, большее 20, есть сумма квадратов цифр некоторого квадрата.

---