Квадрат суммы чисел равен сумме кубов чисел

[VAL]

maxal в сообщении #348993 писал(а):

VAL в сообщении #348990 писал(а):

Это общее соображение. Аккуратнее пока не доказывал.

С удовольствием посмотрю на доказательство. (что-то мне подсказывает, что тут отнюдь не всё так просто)

Если удаляется одно слагаемое, то требуемое неравенство доказывается в одну строчку.
А дальше по индукции :)

[Droog_Andrey]

VAL в сообщении #348987 писал(а):

Любое нетривиальное решение с попарно различными (натуральными) числами должно получаться из тривиального $(1+2+\cdots+n)^2=1^3+2^3+\cdots+n^3$ выбрасыванием нескольких слагаемых, но не последнего. Но при этом левая часть всегда будет меньше правой.

Пусть мы выбросили очередное слагаемое $k$. Тогда левая часть $l^2$ уменьшается на $2kl-k^2$. Для того, чтобы правая часть уменьшилась на меньшую величину, необходимо $k^2+k-2l < 0$, а это возможно лишь при $k < \sqrt{2l}-\frac12$, так что индукция не прокатит.

[maxal]

Вроде придумал доказательство.

Лемма. Для натуральных чисел $a,b$, $a+1 < b-1$, справедливо неравенство:

$$(a+1)^3 + (b-1)^3 < a^3 + b^3.$$

Доказательство очевидно.

Предположим, что у нас есть решение

$$(\star)\qquad\qquad\left(\sum_{k=1}^n a_k\right)^2 = \sum_{k=1}^n a_k^3,$$

в котором $a_1<a_2<\dots<a_n$ является натуральными. Если в отрезке $[a_1, a_n]$ имеется две "дырки", то есть, два натуральных числа $a_1<x<y<a_n$, которые не являются элементами множества $\{ a_k \}$, то беря ближайший к $x$ слева элемент $a_i$ и ближайший к $y$ справа элемент $a_j$, заключаем, что $a_i+1 < a_j -1$ также являются дырками. Увеличивая $a_i$ на 1 и уменьшая $a_j$ на 1, мы не изменяем сумму $\sum a_k$, но уменьшаем сумму $\sum_k a_k^3$ (по лемме), причём все $a_k$ по-прежнему являются попарно различными натуральными числами.

Будем осуществлять подобные операции, покуда у нас имеются две дырки. Заметим, что величина "разброса" $\sum_{k<k'} (a_{k'}-a_k)$ при каждой такой операции уменьшается как мининимум на 2. Поэтому рано или позно мы придем к ситуации с максимум одной дыркой и неравенством

$$\left(\sum_{k=1}^n a_k\right)^2 \geq \sum_{k=1}^n a_k^3,$$

причем равенство имеется только в том случае, когда набор $a_1,\dots,a_n$ - исходный.

Если дырок нет, то $a_k = m+k$ для всех $k=1,2,\dots,n$ и некоторого $m\geq 0$. Тогда для $v=T_m=\sum_{i=1}^m i$ и $u= T_{m+n}$ имеем

$$\left(\sum_{k=1}^n a_k\right)^2 = (u - v)^2 \geq u^2 - v^2 = \sum_{k=1}^n a_k^3.$$

Сокращая на $u-v$, получаем $u-v\geq u+v$ и, следовательно, $v=m=0$. В этом случае $a_k=k$ представляют наш исходный набор.

Если дырка одна, то аналогично для $u=T_{m+n+1}$, $v=T_m$ и некоторой дырки $s$, $m+2\leq s\leq m+n$, имеем:

$$(u - v-s)^2 \geq u^2 - v^2-s^3$$

или

$$s^3 + s^2 - 2(u-v)s - 2v(u-v) \geq 0$$

Найдем максимум левой части как функции от $s\in [m+2,m+n]$. Производная равна $3s^2 + 2s - 2(u-v)$, и её корнями являются $s=\frac{-1\pm \sqrt{1+6(u-v)}}3$. Так как меньший корень (соответствующий локальному максимуму) отрицательный, то максимум в отрезке $[m+2,m+n]$ достигается на одном из его концов. Поэтому должно выполняться хотя бы одно из неравенств:

$$(m+2)^3 + (m+2)^2 - 2(u-v)(m+2) - 2v(u-v) \geq 0$$

или

$$(m+n)^3 + (m+n)^2 - 2(u-v)(m+n) - 2v(u-v) \geq 0.$$

Первое неравенство равносильно:

$$(3 m^2 - \frac{9}{2} m^2 n) + (9m-\frac{17}2 m n) + (8-6n) - \frac{3}{2}mn^2 - 2n^2 - m^3 n - \frac{1}{2} m^2 n^2\geq 0$$

но, как нетрудно видеть, все скобки и остальные слагаемые в нём отрицательны (учитывая $n\geq 2$).
Второе неравенство и того проще:

$$-\frac{3}2 m^2 n - \frac{1}{2} m n^2 - 3m^2 - \frac{9}2 m n - 2n^2 - 3m- 2n-m^3n - \frac{1}2 m^2 n^2\geq 0$$

в нем все слагаемые отрицательны, и поэтому выполняться оно не может.

Итак, решением $(\star)$, где все натуральные числа $a_k$ различны, единственно и является набором первых $n$ натуральных чисел.

[VAL]

maxal в сообщении #349288 писал(а):

Вроде придумал доказательство.

Ну вот, я же говорил: "Очевидно!"

[Батороев]

Наиболее очевидным этот факт становится, если использовать графическую интерпретацию, которую я уже ранее предлагал в одной из тем.

Коротко напомню ее суть:

Рисуем окружности "горкой", как они обычно изображаются для отображения треугольных чисел.
Соединяем центры всех соседних окружностей.
Получили равносторонний треугольник, состоящий из маленьких.
Отмечаем 1-й ряд сверху - это $1^3$.
Затем отмечаем следующие 2 ряда - это $2^3$ маленьких треугольников.
Следующие 3 ряда дают $3^3$
и т.д.

Рассматриваемый ныне вопрос на этой графической интерпретации формулируется следующим образом:
"Где больше маленьких треугольников - в $k$ рядах, находящихся в треугольнике и соответствующих $k^3$,
или в $k$ рядах, находящихся в основании большого треугольника?"

[maxal]

A158649(14) = 69459

Интуиция подсказывает, что вычислять элементы этой последовательности можно гораздо быстрее чем тупым перебором, но пока что-то не получается добиться существенного ускорения.

[maxal]

maxal в сообщении #349288 писал(а):

Предположим, что у нас есть решение

$$(\star)\qquad\qquad\left(\sum_{k=1}^n a_k\right)^2 = \sum_{k=1}^n a_k^3,$$

в котором $a_1<a_2<\dots<a_n$ является натуральными.

...

Итак, решением $(\star)$, где все натуральные числа $a_k$ различны, единственно и является набором первых $n$ натуральных чисел.

Я закинул эту задачу в Crux Mathematicorum, и там некто M. Bataille построил такое разложение:

$$\sum_{k=1}^n a_k^3 - \left(\sum_{k=1}^n a_k\right)^2 = \sum_{k=1}^n a_k \sum_{j=1}^k (a_j + a_{j-1})(a_j - a_{j-1} -1),$$

где доопределено $a_0=0$. Отсюда моментально следует, что для $a_0=0<a_1<a_2<\dots<a_n$ это выражение неотрицательно и равно нулю только если равны нулю все $a_j - a_{j-1} -1$, то есть, $a_j=a_{j-1}+1$ для всех $j$. Значит, $a_j=j$, ч.т.д.

Вот такое по-настоящему олимпиадное решение в две строчки!

[lopkityu]

Droog_Andrey в сообщении #240718 писал(а):

Интересно было бы найти нетривиальное решение, где все $a_k$ различны.

Если положить, что $ a_{k} $ - разные натуральные, то методом матиндукции доказывается неравенство $ \sum\limits_{k=1}^{n}a_{k}^3\geq\left( \sum\limits_{k=1}^{n}a_{k} \right)^2 $, причем равенство достигается лишь в том случае, когда $ a_{k}=k, 1\leq k\leq n $. Поэтому для поиска нетривиальных решений разумно сделать допущение, что не все числа разные.

-- 20.05.2015, 08:26 --

Прошу прощения, не прочитал последние сообщения, думал, что это еще не доказано.