2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение25.08.2010, 20:12 
Sasha2 в сообщении #347222 писал(а):
Вот так с ходу непонятно...


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

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

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

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение25.08.2010, 20:29 
Аватара пользователя
Не вижу, как может реализоваться Ваш случай. В первом произведении сумма сомножителей, а значит сумма всех слагаемых, не равна сумме сомножителей из второго произведения.
$17\ne 15$

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение25.08.2010, 20:49 
Да понял, виноват.
Ну а как-то это можно связать с возрастанием или убыванием этих последовательностей?

-- Ср авг 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$, которая явласб бы наименьшей, но при которой неравенство Коши-Шварца все еще выполняется.
Кстати обязательно ли правой части быть исключительно той, которая и указывается в соответствующей теореме?

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение26.08.2010, 06:40 
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)$
Правильно? :roll:
Или Вы не про то?

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

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение10.09.2010, 03:18 
Аватара пользователя
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, шансы такой возможности мизерно малы.

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение10.09.2010, 04:33 
maxal в сообщении #350923 писал(а):
Sasha2 в сообщении #347222 писал(а):
Как их надо расставить (переставить), чтобы произведение $(a_1+a_2+...+a_n)(a_{n+1}+a_{n+2}+...+a_{2n})$ было наибольшим (наименьшим)?

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

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение10.09.2010, 04:39 
Аватара пользователя
venco в сообщении #350929 писал(а):
А не наоборот?

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

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

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение12.09.2010, 19:20 
$C_{2n}^n /2$ У нас в обоих множествах по n элементов

 
 
 
 Re: По мотивам перестановочного неравенства
Сообщение18.09.2010, 19:44 
Аватара пользователя
Cash в сообщении #351674 писал(а):
А разве требовалось найти эффективный алгоритм?

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

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group