По мотивам перестановочного неравенства

[Sasha2]

Вот так с ходу непонятно, допустим у нас имеется $2n$ положительных вещественных чисел.
Как их надо расставить (переставить), чтобы произведение $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ было наибольшим (наименьшим)?
Наверно тоже, как и в перестановочном обе последовательности должны быть однонаправленными (разнонаправленными). Но так вот непонятно, как подходить к решению этой задачи.

P.S. Нетрудно видеть, что данная конструкция напоминает правую (большую часть) неравенства Коши-Шварца.
Вот хотелось бы узнать можно ли перестановками, так сказать, несколько улучшить это классическое неравенство.

[mihailm]

Sasha2 в сообщении #347222 писал(а):

Вот так с ходу непонятно...

Пора менять введение)))

Чтобы произведение было наибольшим надо сделать оба сомножителя максимально близкими

[Sasha2]

Я это знаю, но это действует в том случае, когда изменение может носить непрерывный характер.
В данном случае это отнюдь не факт.
Где гарантия, что не встретится случай $4\cdot13 $и $5\cdot10$

[gris]

Не вижу, как может реализоваться Ваш случай. В первом произведении сумма сомножителей, а значит сумма всех слагаемых, не равна сумме сомножителей из второго произведения.
$17\ne 15$

[Sasha2]

Да понял, виноват.
Ну а как-то это можно связать с возрастанием или убыванием этих последовательностей?

-- Ср авг 25, 2010 22:00:25 --

Да, пожалуй тут без левой части неравенства Коши не обойтись.
Я вообщем то вопрос имел с таким прицелом.
Вот левая часть неравенства Коши-Шварца $(a_1b_1+a_2b_2+...a_nb_n)^2$.
Теперь перемешаем все числа $a_i$ и $b_i$.
Далее из них образуем вот такое произведение $(x_1^2+x_2^2+...x_n^2)(y_1^2+y_2^2+...y_n^2)$, ну понятно, что это правая часть неравенства Коши-Шварца.
Так вот хотелось бы узнать, как найти такую комбинацию $x_i$ и $y_i$, которая явласб бы наименьшей, но при которой неравенство Коши-Шварца все еще выполняется.
Кстати обязательно ли правой части быть исключительно той, которая и указывается в соответствующей теореме?

[Sonic86]

Sasha2 писал(а):

Вот так с ходу непонятно, допустим у нас имеется $2n$ положительных вещественных чисел.
Как их надо расставить (переставить), чтобы произведение $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ было наибольшим (наименьшим)?

Ну если взять $x=a_1+a_2+...+a_n, y=a_{n+1}+a_{n+2}+...+a_{2n}$, то имеем задачу $x+y = \text{const}$, $xy \to \min (\max)$
Правильно?
Или Вы не про то?

[Sasha2]

Нет, конечно я не про то.
Я сначала тоже думал, что примерно такой подход может дать решение для этой задачи.
Вопрос тут в другом.
Вот имеются левая часть неравенства Коши-Шварца. Из чисел которые ее образуют несколько по другому формируется и правая (большая часть этого неравенства). Так вот хотелось бы узнать можно ли перестановкой отдельных слагаемых из одной скобки в другую уменьшить правую часть, но так, чтобы она все еще оказывалась больше левой.
Грубо говоря, является ли та стандартная правая часть минимальным значением из всех аналогичных произведений сумм квадратов, которые больше левой части этого же неравенства.

[maxal]

Sasha2 в сообщении #347222 писал(а):

Как их надо расставить (переставить), чтобы произведение $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ было наибольшим (наименьшим)?

Как сделать наименьшим - очевидно. А вот с наибольшим значением проблема - в общем случае не существует эффективного способа это выяснить, так как эта задача эквивалентна NP-полной задаче Subset sum problem. Если вы опишите как максимизировать $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ путем перестановки членов, то вы тем самым решите важный случай Subset sum problem, шансы такой возможности мизерно малы.

[venco]

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

Sasha2 в сообщении #347222 писал(а):

Как их надо расставить (переставить), чтобы произведение $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ было наибольшим (наименьшим)?

Как сделать наибольшим - очевидно. А вот с наименьшим значением проблема

А не наоборот?

[maxal]

venco в сообщении #350929 писал(а):

А не наоборот?

Конечно. Исправил.

[Cash]

А разве требовалось найти эффективный алгоритм?
Для решения поставленной задачи достаточно и полного перебора будет. Из имеющихся $2^2^n-2$ подмножеств выбираем то, у которого сумма элементов наиболее близка к $S/2$.

[Null]

$C_{2n}^n /2$ У нас в обоих множествах по n элементов

[maxal]

Cash в сообщении #351674 писал(а):

А разве требовалось найти эффективный алгоритм?

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