Максимум суммы

[ewert]

MrDindows в сообщении #430903 писал(а):

Может быть лучше $a_1=\frac{1}{2}, a_2=\frac{1}{2}$, а все остальные равны нулю.
Тогда сумма $\frac{1}{4}$

Да, гораздо лучше. Я там чего-то зазевался. Стал рассматривать почему-то $xy$, хотя надо было смотреть на $ux+xy+yv=(x+v)(y+u)+\mathrm{const}$ (подразумевая, что икс с игреком меняются, в то время как всё остальное зафиксировано). Соответственно, начиная с четырёх слагаемых -- ответ должен быть действительно одна четверть, для трёх -- одна треть и для двух -- одна вторая.

[Null]

Для двух получается $a_1 a_2 +a_2 a_1$ - максимиум $\frac{1}{2}$.
При n>2 ответ 0.25

[spaits]

Sonic86 в сообщении #430924 писал(а):

Очень маленький совет - при поиске экстремальных значений симметрических функций всегда смотрите, чему равно значение этой функции при одинаковых аргументах (в данном случае значение аргументов, когда они одинаковы, находите из данного ограничения)

При одинаковых числах (для $n$ числа равны $\frac1n$) сумма попарных произведений чисел равна $C_n^2\cdot \frac1{n^2}=\frac{n(n-1)}2\cdot\(\frac1{n^2}=\frac12\cdot(1-\frac1n)$.
Эта сумма имеет предел $\frac12$ при $n$, стремящемся к бесконечности, но не имеет наибольшего значения.

[MrDindows]

spaits в сообщении #430955 писал(а):

Sonic86 в сообщении #430924 писал(а):

Очень маленький совет - при поиске экстремальных значений симметрических функций всегда смотрите, чему равно значение этой функции при одинаковых аргументах (в данном случае значение аргументов, когда они одинаковы, находите из данного ограничения)

При одинаковых числах (для $n$ числа равны $\frac1n$) сумма попарных произведений чисел равна $C_n^2\cdot \frac1{n^2}=\frac{n(n-1)}2\cdot\(\frac1{n^2})=\frac12\cdot(1-\frac1n)$.
Эта сумма имеет предел $\frac12$ при $n$, стремящемся к бесконечности, но не имеет наибольшего значения.

У нас не все попарные произведения, а произведения $a_ia_{i+1}$

[spaits]

MrDindows в сообщении #430958 писал(а):

При одинаковых числах (для числа равны ) сумма попарных произведений чисел равна .
Эта сумма имеет предел при , стремящемся к бесконечности, но не имеет наибольшего значения.

Да, я уже заметила. Спасибо. При одинаковых числах искомая сумма произведений равна $n\cdot\frac1{n^2} = \frac{1}{n}$.
Осталось доказать, что при разных числах для всех $n$ сумма произведений меньше $\frac12$.

[Sonic86]

spaits писал(а):

При одинаковых числах (для $n$ числа равны $\frac1n$) сумма попарных произведений чисел равна $C_n^2\cdot \frac1{n^2}=\frac{n(n-1)}2\cdot\(\frac1{n^2}=\frac12\cdot(1-\frac1n)$.
Эта сумма имеет предел $\frac12$ при $n$, стремящемся к бесконечности, но не имеет наибольшего значения.

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

[arqady]

Andrey173 в сообщении #430870 писал(а):

Пусть даны n неотрицательных чисел $a_1, a_2, ..., a_n$ и их сумма равна 1.
Найти наибольшее возможное значение суммы:$a_1a_2+a_2a_3+...+a_na_1$

С чего начать? Мне почему-то кажется, что $\frac{1}{3}$

Начать можно со случая, когда $n$ чётно и тогда
$a_1a_2+a_2a_3+...+a_na_1\leq\left(a_1+a_3+...+a_{n-1}\right)\left(a_2+a_4+...+a_n\right)\leq$
$\leq\left(\frac{a_1+a_2+...+a_n}{2}\right)^2=\frac{1}{4}$.

[sup]

Итак, для $n=2$ максимум 1/4. Для $n=3$ -- 1/3. Пусть $n=4$ заметим, что
$ab+bc+cd+da = b(a+c)+d(a+c) = (a+c)(b+d)$
Отсюда и для $n=4$ максимум 1/4.
Теперь докажем по индукции, что и при $n>4$ максимум 1/4.
Без потери общности можно считать, что $a_n$ минимальное число из всех $a_i$ (иначе, циклически перенумеруем). Следовательно $a_n \leq 1/n \leq 1/5$. Далее
$S_n = a_1a_2+a_2a_3+ ... + a_{n-2}a_{n-1} + a_{n-1}a_{1} -a_{n-1}(a_1-a_n)+a_na_1 \leq (1-a_n)^2/4-a_n(a_1-a_n)+a_na_1 \leq (1-a_n)^2/4 +a_n^2 \leq 1/4$

[ewert]

Null в сообщении #430950 писал(а):

При n>2 ответ 0.25

При $n>3$.

sup в сообщении #431018 писал(а):

Итак, для $n=2$ максимум 1/4.

Максимум $1/2$.

-- Пн апр 04, 2011 12:56:55 --

Да, индукция. Предположим:

$4(x_1x_2+x_2x_3+\ldots+x_nx_1)\leqslant(x_1+x_2+\ldots+x_n)^2.$

Надо доказать:

$4(x_1x_2+x_2x_3+\ldots+x_nx_{n+1}+x_{n+1}x_1)\leqslant(x_1+x_2+\ldots+x_n+x_{n+1})^2.$

Для этого достаточно:

$x_{n+1}^2+2x_{n+1}(x_1+x_2+\ldots+x_n)\geqslant4(x_nx_{n+1}+x_{n+1}x_1-x_nx_1)\quad\Longleftrightarrow$

$\Longleftrightarrow\quad x_{n+1}^2+2x_{n+1}(-x_1+x_2+\ldots+x_{n-1}-x_n)+4x_nx_1\geqslant0.\qquad(*)$

Всегда можно выбрать циклическую перестановку чисел $x_1,x_2,\ldots,x_n,x_{n+1}$ так, чтобы оказалось $x_1+x_n\leqslant x_2+x_{n-1}$. Тогда все слагаемые в левой части $(*)$ неотрицательны и, следовательно, это неравенство действительно выполняется.

[ewert]

Кстати, чтобы уж добить тему. С $n=2,3,4$ всё более-менее ясно. А вот для $n\geqslant5$: на каких (и только на каких) наборах чисел достигается максимум?...

[mserg]

Можно воспользоваться принципом доминирования, который понятен на «бытовом» уровне:
1. Если все числа не равны нулю, то находим число, у которого сумма соседей («слева» + «справа») минимальна. Прибавляем его к элементу, находящемуся через один в сторону от наибольшего соседнего числа. Само число обнуляем.
2. Если среди чисел есть нули, то их можно задвинуть в конец – сумма не уменьшится. Нулевые элементы больше не рассматриваем.
3. Берем «последний» элемент и прибавляем его к пре-предпоследнему; последний элемент обнуляем. Сумма от этого увеличится. Так можно дойти до трех ненулевых элементов.
4. Получаем тривиальную задачу на оптимум с тремя переменными. Точнее с двумя, так как задача содержит только суммы крайних ненулевых элементов и центральный элемент. Ответ 0.25, если n больше трех. Оптимум достигается, если элементов три с 0.5 посередине, и суммой 0.5 крайних элементов.

[ewert]

mserg в сообщении #431123 писал(а):

Оптимум достигается, если элементов три с 0.5 посередине, и суммой 0.5 крайних элементов.

В принципе да, только надо бы ещё доказать, что оптимум достигается только на таких комбинациях. Тут скользкий момент -- это первый пункт. И действительно скользкий: для $n=4$ последнее утверждение (что только на таких) неверно. Да, и второй пункт с этой точки зрения требует тоже чуть более аккуратного изложения.

[mserg]

Что-то я не вкурил, где косяк то?
Для n=4 есть контрпример?

[ИСН]

1/4, 1/4, 1/4, 1/4.

[ewert]

mserg в сообщении #431156 писал(а):

Для n=4 есть контрпример?

Естественно. В том смысле, что там четвертинка достигается не обязательно тогда, когда один из элементов нулевой. Там критерий -- это $x_1+x_3=x_2+x_4=\frac12$.