Минимум суммы при фиксированной сумме квадратов

[maxal]

Определим функцию на множестве неотрицательных целых чисел:

$f(0) = 0;$

$$f(n) = \min_{m_1^2 + \dots + m_k^2 = n\atop k, m_1, \dots, m_k\in\mathbb{N}} m_1 + \dots + m_k\qquad \mbox{для всех } n>0.$$

Докажите, что для всех достаточно больших $n$ справедлива формула:

$$f(n) = \lfloor \sqrt{n}\rfloor + f\left(n - \lfloor \sqrt{n}\rfloor^2\right).$$

[Kid Kool]

Фактически, нужно доказать, что максимальное из $m_i$ равно $\lfloor \sqrt{n}\rfloor$.

[Руст]

По определению $f(0)=0$,

$$ (1) \ \ f(n)=\min_{1\le k\le \sqrt n}(k+f(n-k^2)).$$

Воспользовавшись этим, докажем по индукции
(2) $f(n)\le \sqrt n +\sqrt{3\sqrt n}$.
Для этого достаточно проверить $k+\sqrt{n-k^2}+\sqrt{3\sqrt{n-k^2}}\le \sqrt n+\sqrt{3\sqrt n}$ при $k=[\sqrt n]$.
Так как $n-k^2<2\sqrt n$ неравенство доказывается индукцией, если
$n>\frac{324}{(\sqrt{3}-\sqrt{2})^8}=3 111 047,96..$ т.е. при $n\ge 3 111 048$.На самом деле не сложно проверить это неравенство и при малых n и доказать, что оно всегда выполняется. Отсюда получается, что в определении (1) всегда надо брать $k=[\sqrt n ]$.

[maxal]

Руст писал(а):

На самом деле не сложно проверить это неравенство и при малых n и доказать, что оно всегда выполняется. Отсюда получается, что в определении (1) всегда надо брать $k=[\sqrt n ]$.

Это неверное утверждение.

Добавлено спустя 1 минуту 15 секунд:

Kid Kool писал(а):

Фактически, нужно доказать, что максимальное из $m_i$ равно $\lfloor \sqrt{n}\rfloor$.

Нет. Нужно доказать, что его можно взять равным $\lfloor \sqrt{n}\rfloor$, что впрочем не отрицает существования других оптимальных вариантов.

Добавлено спустя 1 час 9 минут 28 секунд:

Наименьший контр-пример к этой формуле - $n=32$.
Если отхватить по максимуму:
$32 = 5^2 + 2^2 + 1^2 + 1^2 + 1^2$, то сумма $10$ (как справедливо заметил Kid Kool), в то время как минимум достигается на $32 = 4^2 + 4^2$ с суммой равной $8$.

[Kid Kool]

maxal писал(а):

Наименьший контр-пример к этой формуле - $n=32$.

Этот контрпример является контрпримером и к Вашей формуле : ))

Добавлено спустя 1 минуту 2 секунды:

maxal писал(а):

$32 = 5^2 + 2^2 + 1^2 + 1^2 + 1^2$,

Сумма, вообще-то, 10.

[maxal]

Нет. Это контр-пример к последнему утверждению Рустема. А в "моей формуле", как вы ее называете, оговорена ее применимость только для достаточно больших $n$. Очевидно, что $n=32$ не является достаточно большим.

P.S. Сумму поправил.

Добавлено спустя 40 минут 28 секунд:

Руст писал(а):

По определению $f(0)=0$,

$$ (1) \ \ f(n)=\min_{1\le k\le \sqrt n}(k+f(n-k^2)).$$

Воспользовавшись этим, докажем по индукции
(2) $f(n)\le \sqrt n +\sqrt{3\sqrt n}$.
Для этого достаточно проверить $k+\sqrt{n-k^2}+\sqrt{3\sqrt{n-k^2}}\le \sqrt n+\sqrt{3\sqrt n}$ при $k=[\sqrt n]$.
Так как $n-k^2<2\sqrt n$ неравенство доказывается индукцией, если
$n>\frac{324}{(\sqrt{3}-\sqrt{2})^8}=3 111 047,96..$ т.е. при $n\ge 3 111 048$.

Кстати, что здесь является базой индукции?
И как из (2) (в предположении, что оно доказано) следует требуемое свойство:

$$f(n) = \lfloor \sqrt{n}\rfloor + f\left(n - \lfloor \sqrt{n}\rfloor^2\right)$$

[Руст]

Верна оценка
(2) $f(n)<\sqrt n+2n^{1/4}+1.6$
Последнее n когда $[\sqrt n]=l>k$ есть n=24961. Из оценки (2) следует, что $k=l$ или $k=l-1$.
А начиная с некоторого n (n>24961) исключается последний случай вследствие оценки сверху
$\sqrt n\le f(n)<\sqrt n +2n^{1/4}+1.6$ сравнивая вычисления f(n) при k=l и при k=l-1.