Олимпиада имени Леонарда Эйлера2009-2010 учебный год, I тур заключительного этапа

В вершинах куба расставили числа $1^{2}, 2^2, \dots , 8^2$ (в каждую из вершин — по одному числу). Для каждого ребра посчитали произведение чисел в его концах. Найдите наибольшую возможную сумму всех этих произведений. ( Д. Фон-дер-Флаасс )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 9420.
Решение. Раскрасим вершины куба в два цвета так, чтобы концы каждого ребра были разноцветными. Пусть в вершинах одного цвета стоят числа $a_1, a_2, a_3, a_4$, а в вершинах другого — числа $b_1, b_2, b_3, b_4$, причём числа с одинаковыми номерами стоят в противоположных вершинах. Тогда, как легко проверить, указанная в условии сумма произведений будет равна $(a_1+a_2+a_3+a_4)(b_1+b_2+b_3+b_4) - (a_1b_1+a_2b_2+a_3b_3+a_4b_4)$. По неравенству о средних $(a_1+a_2+a_3+a_4)(b_1+b_2+b_3+b_4) \leq (a_1+a_2+a_3+a_4+b_1+b_2+b_3+b_4)^2/4 = (1^2+2^2+ \dots +8^2)^2/4 = 10404$, причём равенство достигается только при $$a_1+a_2+a_3+a_4 = b_1+b_2+b_3+b_4. \quad (1)$$ С другой стороны, сумма $a_1b_1+a_2b_2+a_3b_3+a_4b_4$, где $a_i$ и $b_i$ — числа $1^2, 2^2, \dots , 8^2$, минимальна тогда, когда $8^2$ умножается на $1^2$, $7^2$ — на $2^2$, $6^2$ — на $3^2$, $5^2$ — на $4^2 (2)$. В самом деле, пусть $8^2$ умножается на $a^2 \ne 1^2$, а $1^2$ — на $b^2$. Понятно, что умножив $8^2$ на $1^2$, а $a^2$ — на $b^2$, мы уменьшим сумму $a_1b_1+a_2b_2+a_3b_3+a_4b_4$. Затем аналогично показываем, что мы уменьшим сумму, умножив $7^2$ на $2^2$, и т.д.
Как ни удивительно, можно добиться одновременного выполнения условия максимальности (1) и условия минимальности (2): для этого надо в вершины одного цвета поставить числа $1^2$, $4^2$, $6^2$ и $7^2$, а в вершины другого — остальные таким образом, чтобы $8^2$ и $1^2$, $7^2$ и $2^2$, $6^2$ и $3^2$, $5^2$ и $4^2$ стояли в противоположных вершинах. Понятно, что такая расстановка и даст искомый максимум сумм произведений, равный $(1^2+4^2+6^2+7^2)^2 - (8^2 \cdot 1^2+7^2 \cdot 2^2+6^2 \cdot 3^2+5^2 \cdot 4^2) = 102^2 - 984 = 9420$.
Замечание. Тот факт, что числа $1^2, 2^2, \dots , 8^2$ можно разбить на две группы по 4 числа с равными суммами чисел, не случаен. Заметим, что $(n+1)^2 - n^2 = 2n+1$, поэтому $((n+3)^2 - (n+2)^2) - ((n+1)^2 - n^2) = (2n+5) - (2n+1) = 4$ при любом $n$. Отсюда $(1^2 - 2^2 - 3^2+4^2) - (5^2 -6^2 -7^2+8^2) = 1^2 -2^2 -3^2+4^2 -5^2+6^2+7^2 - 8^2 = 4 - 4 = 0$.