Новогодняя загадка про число 2016

[Ktina]

Какое наименьшее число точных четвёртых степеней нужно сложить, чтобы получилось 2016?

С Новым Годом!

[Mihr]

(Халявное решение)

Перебирать варианты лень.
Если Excel не ошибается, то для оптимального решения потребуется 16 слагаемых: $6^4+2\cdot4^4+13\cdot2^4=2016$
А "жадный" алгоритм даёт решение, близкое к оптимальному - 17 слагаемых: $6^4+5^4+3^4+14\cdot1^4=2016$

[fiviol]

Excel не ошибается.
Четвертые степени нечетных чисел дают остаток 1 при делении на 16, а 2016 и четвертые степени четных - 0. Поэтому нечетных слагаемых должно быть не меньше 16, но для 16 слагаемых решение уже есть.
Значит будем пользоваться только четными слагаемыми. Сократив 2016 и все слагаемые на 16, получим тот же вопрос, что в задаче, но для 126. При делении на 16 число 126 дает остаток 14, значит нужно 14 нечетных слагаемых. Если слагаемое 81 есть, то нечетные слагаемые дают 94, а если его нет, то 14. Четные слагаемые тогда дают 32 или 112, что четвертыми степенями не является, поэтому пятнадцатью слагаемыми не обойтись.

[Ktina]

fiviol