[D40] простое (с виду) неравенство...
Sergei Markelov
даны три положительных числа a, b и c, сумма которых равна 3. Найти
максимум выражения:
a b a c b c
S = ------ + ------ + ------
2 2 2
c + 3 b + 3 a + 3
Для удобства то же выражение в других форматах:
\text{S}=\frac{bc}{a^{2}+3}+\frac{ca}{b^{2}+3}+\frac{ab}{c^{2}+3}
S=a*b/(c^2+3)+a*c/(b^2+3)+b*c/(a^2+3)
Задача на первый взгляд кажется обычным упражнением - но при попытке
доказать открывается нечто неожиданное...
Если кто-нибудь решит (пусть даже и громоздко), напишите мне,
пожалуйста.
Спасибо.
Сергей Маркелов
Boris Shklyaev
SM> даны три положительных числа a, b и c, сумма которых равна 3. Hайти
SM> максимум выражения:
SM> a b a c b c
SM> S = ------ + ------ + ------
SM> 2 2 2
SM> c + 3 b + 3 a + 3
SM> Задача на первый взгляд кажется обычным упражнением - но при попытке
SM> доказать открывается нечто неожиданное...
банка пива? :))
SM> Если кто-нибудь решит (пусть даже и громоздко), напишите мне,
SM> пожалуйста.
очевидно, a>0,b>0,c>0. иначе из 3-х слагаемых останется только одно, или из
сложения получится вычитание, а это, понимаешь, не круто. далее, что еще можно
сказать. квадрат растет быстрее отрезка, поэтому больше 1-цы придавать значения
параметрам нельзя. меньше единицы - тоже, т.к. получим в числителе величину
меньше 1. остается вариант - a=b=c=1.
максимум здесь = 3/4.
кто выжмет больше? :)
ps. это уравнение напомнило мне параметрическое уравнение эллипсоида.
а объем эллипсоида наибольший при равенстве всех параметров, т.е. шар
имеет наибольший объем из всех разновидностей эллипсоида.
если не так, поправьте меня неуча.
_/Good Luck, Sergei./_
... [*ФИТ-151*]-[_Zenwalk Linux_]-[_винмоздай_]-[/дзен/]
Sergei Markelov
> SM> даны три положительных числа a, b и c, сумма которых равна 3. Hайти
> SM> максимум выражения:
> SM> a b a c b c
> SM> S = ------ + ------ + ------
> SM> 2 2 2
> SM> c + 3 b + 3 a + 3
> SM> Задача на первый взгляд кажется обычным упражнением - но при попытке
> SM> доказать открывается нечто неожиданное...
>
> банка пива? :))
>
> SM> Если кто-нибудь решит (пусть даже и громоздко), напишите мне,
> SM> пожалуйста.
>
> очевидно, a>0,b>0,c>0. иначе из 3-х слагаемых останется только одно,
> или из сложения получится вычитание, а это, понимаешь, не круто.
> далее, что еще можно сказать. квадрат растет быстрее отрезка,
> поэтому больше 1-цы придавать значения параметрам нельзя. меньше
> единицы - тоже, т.к. получим в числителе величину меньше 1. остается
> вариант - a=b=c=1. максимум здесь = 3/4. кто выжмет больше? :)
Борис, добрый день!
В том и фокус в этой задаче, что ответ 3/4 неправильный... Можно
сделать больше ;-).
Сергей Маркелов
Alexander Derazhne
Если положить a==0 и пренебречь ограничением суммы, то "изобары"
оставшегося члена будут представлять собой гиперболы в полскости bc.
То-же самое можно сказать и об остальных плоскостях.
Равенство суммы трём означает, что решение ищётся исключительно в
соответствующей плоскости, отсекающей трёхгранную пирамиду с началом
координат в вершине.
Исходя из симметрии, интуитивно, экстремум должен лежать либо на
пересечении этой плоскости с координатными плоскостями, либо в центре
основания пирамиды. Но это нестрогая догадка.
Мне кажется, что стоит попробовать развернуть систему координат abc и
преобразовать в цилиндрическую - удаление плоскости a+b+c=3 от начала
координат (константа) и полярные координаты в этой плоскости. Обычно
такие "центральносимметричные" задачи легче решаются именно в полярной
системе координат...
Nick Kazimirov
Вы писали 6 августа 2007 г., 21:33:54:
SM> On Mon, 6 Aug 2007, Boris Shklyaev wrote:
>> SM> даны три положительных числа a, b и c, сумма которых равна 3. Hайти
>> SM> максимум выражения:
>> SM> a b a c b c
>> SM> S = ------ + ------ + ------
>> SM> 2 2 2
>> SM> c + 3 b + 3 a + 3
>> SM> Задача на первый взгляд кажется обычным упражнением - но при попытке
>> SM> доказать открывается нечто неожиданное...
SM> В том и фокус в этой задаче, что ответ 3/4 неправильный... Можно
SM> сделать больше ;-).
точно, можно
Поскольку 3/4 достигаются в точках (1,1,1) и (0,3/2,3/2), то хочется
провести соединяющий их отрезок и посмотреть, что происходит с
функцией вдоль отрезка.
Берем a=x, b=(3-x)/2, c=(3-x)/2. Подставляем:
S= (3/4)(3-x)(5x^3 +3x+21+3x^2)/(21-6x+x^2)(x^2+3)
S'=(27/2)(x^2+7)(x^2-12x+3)(x-1)^2/(x^2-6x+21)^2 (x^2+3)^2
x1=1, x2=6-sqrt(33).
Первая точка соответствует как раз набору (1,1,1), и в ней экстремума
нет, а во второй есть экстремум. Поэтому она является подозрительной
на экстремум для функции S. Значение в данной точке примерно равно
0.757925, т.е. чуть больше 3/4.
Если посчитать градиент функции Лагранжа (при поиске условного
экстремума), то получится вектор с равными координатами, что и должно
быть. Но вот попытка проверить выпуклость функции через миноры
матрицы вторых производных не увенчалась успехом
Для данной точки в Маткаде знаки главных миноров такие: -,-,+
А по критерию Сильвестра для выпуклости функции нужно, чтобы знаки
чередовались так: -,+,-.
Впрочем, я мог напутать в вычислениях. Вручную считать все эти жуткие
производные невозможно, поэтому использовал символьные вычисления в
Маткаде.
Кстати, численный поиск максимума в том же Маткаде дает то же самое
максимальное значение, но только в других точках, близких к найденной
мной. Для этих точек даже первые производные получаются разными, что
говорит об отсутствии в них экстремума. Возможно, тут дело в
погрешностях вычислений, но разница тех чисел, которые должны
совпадать в теории, составляет примерно 5*10^-5, что вообще-то не так
уж мало.
Поэтому есть подозрение, что максимум достигается на какой-то кривой,
хотя по виду функции (отношение полиномов) этого не скажешь.
Так что, пока самой убедительной точкой максимума выглядит
(6-sqrt(33),b,c), где b=c, а также две другие симметричные точки.
--
С уважением,
Nick mailto:nkazi...@gmail.com
Alexander Derazhne
> Мне кажется, что стоит попробовать развернуть систему координат abc и
> преобразовать в цилиндрическую - удаление плоскости a+b+c=3 от начала
> координат (константа) и полярные координаты в этой плоскости. Обычно
> такие "центральносимметричные" задачи легче решаются именно в полярной
> системе координат...
Подзабыл я уже всю эту стереомерию, но вот что получилось:
Если взять радиус R и угол f, отсчитываемые в плоскости a+b+c=3 от точки
(1,1,1) и от вектора (1,1,1)-(0,0,3) соответственно, то
C=1+R*cos(f)*2/sqrt(6);
A=1-R*cos(f)/sqrt(6)+R*sin(f)/sqrt(2);
B=1-R*cos(f)/sqrt(6)-R*sin(f)/sqrt(2);
(проверил бы кто?)
Подставлять это в целевую функцию и решать задачу "упростить" я не
взялся - очень много писанины. Hо, поскольку задача теперь двумерна, то
её можно визуализировать тем-же MathCad'ом :-). Получается, что целевая
функция имеет вид сморщенного зонтика - три гребня и три впадины по
угловой координате (что и ожидалось), а вот по радиальной - впадины
монотонно уходят "вниз", а гребни таки имеют максимум несколько в
стороне от центра! Т.е. получается три симметричных экстремальных точки,
по одной на каждый гребень.
Hо для _точного_ ответа на поставленный вопрос нужно всё-таки
"упростить" выражение для целевой функцции аналитически.
Max Alekseyev
> >> SM> даны три положительных числа a, b и c, сумма которых равна 3. Hайти
> >> SM> максимум выражения:
> >> SM> a b a c b c
> >> SM> S = ------ + ------ + ------
> >> SM> 2 2 2
> >> SM> c + 3 b + 3 a + 3
> >> SM> Задача на первый взгляд кажется обычным упражнением - но при попытке
> >> SM> доказать открывается нечто неожиданное...
>
> SM> В том и фокус в этой задаче, что ответ 3/4 неправильный... Можно
> SM> сделать больше ;-).
>
> точно, можно
> Поскольку 3/4 достигаются в точках (1,1,1) и (0,3/2,3/2), то хочется
> провести соединяющий их отрезок и посмотреть, что происходит с
> функцией вдоль отрезка.
> Берем a=x, b=(3-x)/2, c=(3-x)/2. Подставляем:
> S= (3/4)(3-x)(5x^3 +3x+21+3x^2)/(21-6x+x^2)(x^2+3)
> S'=(27/2)(x^2+7)(x^2-12x+3)(x-1)^2/(x^2-6x+21)^2 (x^2+3)^2
>
> x1=1, x2=6-sqrt(33).
>
> Первая точка соответствует как раз набору (1,1,1), и в ней экстремума
> нет, а во второй есть экстремум. Поэтому она является подозрительной
> на экстремум для функции S. Значение в данной точке примерно равно
> 0.757925, т.е. чуть больше 3/4.
Для a=x2, b=(3-x2)/2, c=(3-x2)/2 у меня получилось
S = 0.7497943180 < 3/4.
> Если посчитать градиент функции Лагранжа (при поиске условного
> экстремума), то получится вектор с равными координатами, что и должно
> быть.
Я вычислил явное выражение для максимума, но оно очень громоздкое и
включает в себя корни многочленов высоких степеней. Позже, возможно,
попробую выразить это значение в радикалах.
Численные же значения такие:
a = b = 1.228083
c = 0.5438310
и S = 0.7524353, что действительно чуть больше 3/4.
Max
Max Alekseyev
>> точно, можно Поскольку 3/4 достигаются в точках (1,1,1) и
>> (0,3/2,3/2), то хочется
>> провести соединяющий их отрезок и посмотреть, что происходит с
>> функцией вдоль отрезка.
>> Берем a=x, b=(3-x)/2, c=(3-x)/2. Подставляем:
>> S= (3/4)(3-x)(5x^3 +3x+21+3x^2)/(21-6x+x^2)(x^2+3)
>> S'=(27/2)(x^2+7)(x^2-12x+3)(x-1)^2/(x^2-6x+21)^2 (x^2+3)^2
>>
>> x1=1, x2=6-sqrt(33).
>>
>> Первая точка соответствует как раз набору (1,1,1), и в ней экстремума
>> нет, а во второй есть экстремум. Поэтому она является подозрительной
>> на экстремум для функции S. Значение в данной точке примерно равно
>> 0.757925, т.е. чуть больше 3/4.
>
> Для a=x2, b=(3-x2)/2, c=(3-x2)/2 у меня получилось
> S = 0.7497943180 < 3/4.
Виноват, я почему-то вычислял с кубами в знаменателях вместо квадратов.
Для квадратов же получается, что
a = 6 - sqrt(33)
b = c = (sqrt(33)-3)/2
дают абсолютно максимальное значение S.
>> Если посчитать градиент функции Лагранжа (при поиске условного
>> экстремума), то получится вектор с равными координатами, что и должно
>> быть.
>
> Я вычислил явное выражение для максимума, но оно очень громоздкое и
> включает в себя корни многочленов высоких степеней. Позже, возможно,
> попробую выразить это значение в радикалах.
> Численные же значения такие:
> a = b = 1.228083
> c = 0.5438310
> и S = 0.7524353, что действительно чуть больше 3/4.
Соответственно, этот результат также относится к кубам.
Max
Sergei Markelov
Александр, добрый день!
Ваши формулы правильные.
У меня есть гипотеза о том, как с их помощью получить правильный ответ
(строгого решения нет). Максимальное значение для S при этом
получается S = (11 sqrt(33) - 45)/24, что приблизительно равно 0.7579.
В Ваших терминах этот ответ достигается при
R = 3/2*22^(1/2) - 5/2*6^(1/2)
1/2 1/2
3 22 - 5 6
R = -----------------
2
и f = Pi/3, либо -Pi/3, либо Pi.
Эти три пары соответствуют тройкам (a,b,c):
a = 6 - sqrt(33), b = c = (sqrt(33) - 3) / 2
a = b = (sqrt(33) - 3) / 2 , c = 6 - sqrt(33)
a = c = (sqrt(33) - 3) / 2 , b = 6 - sqrt(33)
В каждой из которых
a b a c b c
S = ------ + ------ + ------
2 2 2
c + 3 b + 3 a + 3
принимает значение S = (11 sqrt(33) - 45)/24
Как же доказать, что это значение S максимально ?
Я попробовал так: раз минимальные значения образуют правильный
треугольник (или по крайней мере мы это предполагаем), то сделаем
замену
f = 3 u
При этом из нашей функции S(R,f) получится новая функция S1(R,u).
Ясно, что максимум у S1 ровно тот же, что и у S. Однако, у S1 есть
важное преимущество перед S - максимум достигается (если верна наша
гипотеза про то, где достигается максимум у S) только в одной точке -
при том же значении R и u = Pi.
После этого можно попробовать избавиться от тригонометрии, сделав
замену через котангенс половинки (тангенс не пойдет, он в Pi/2
не определен).
Получится дробно-рациональная функция от двух переменных, принимающая
максимальное значение в некоторой одной известной нам точке.
Изменим систему координат так, чтобы значение достигалось в точке
(0;0) и было равно нулю.
Знаменатель в такой ситуации можно игнорировать, получится многочлен
от двух переменных, который достигает максимума в (0,0) и этот
максимум равен 0. В такой ситуации задача выглядит проще - но что
делать дальше я не знаю.
Сергей Маркелов
Alexander Derazhne
Здравствуйте, Сергей!
1. Мне непонятно - откуда взялись _точные_ (с радикалами) значения
для переменных, если аналитического решения не найдено?
2. Если задаться конкретным значением угла, то формулы для A, B и C
упрощаются до 1+Xn*R. При этом должна также сильно упростится форма
производной по R целевой функции. Мне кажется, что таким образом может
быть найдено аналитичское решение. Hо в отношении угла такого упрощения
не просматривается. Т.е. можно привлечь соображения симметрии, но я не
знаю насколько "законным" будет такое рассуждение.
Max Alekseyev
> Sergei Markelov wrote:
>
> Здравствуйте, Сергей!
>
> 1. Мне непонятно - откуда взялись _точные_ (с радикалами) значения
> для переменных, если аналитического решения не найдено?
Вот мое аналитическое решение. Правда, оно основывается на тяжелой артилерии - множителях Лагранжа и базисах Грёбнера.
Вычисления производились в Maple 11.
Сначала определяем систему полиномиальных уравнений, возникающую при применении множителей Лагранжа, то вычисляем числители всех частные производные выражения:
a*b/(c^2+3) + a*c/(b^2+3) + b*c/(a^2+3) + d*(a+b+c-3)
> f:=(a,b,c)->a*b/(c^2+3)+a*c/(b^2+3)+b*c/(a^2+3);
> sys := { numer(diff(f(a,b,c),a)+d), numer(diff(f(a,b,c),b)+d), numer(diff(f(a,b,c),c)+d), a+b+c-3 };
Теперь вычисляем базис Грёбнера этой системы:
> gb:=Groebner[Basis](sys,plex(a,b,c,d));
При этом оказывается, что gb состоит из 10 полиномов, и пара первых факторизуется так:
> nops(gb);
10
> factor(op(1,gb));
(c-3)*(c^2-6*c+21)*(c^2+3)*(432*d^2+18*d-83)*(56*d^2-63*d+18)*(1152*d^5-144*d^4+1488*d^3-80*d^2+612*d-27)*(8*d+3)^2
> factor(op(2,gb));
(c-1)*(c-3)*(c^2-6*c+21)*(c^2+3)*(8*d+3)*(432*d^2+18*d-83)*(56*d^2-63*d+18)*(1152*d^5-144*d^4+1488*d^3-80*d^2+612*d-27)
Как видим, они имеют много общих сомножителей.
Сомножители (c-1)*(c-3)*(c^2-6*c+21)*(c^2+3) интереса не представляют: случаи c=1 и c=3 могут быть легко проанализированы отдельно, а (c^2-6*c+21) и (c^2+3) не имеют действительных корней. Сократим эти множители во всех полиномах в gb.
> p:=(c-1)*(c-3)*(c^2-6*c+21)*(c^2+3);
> pp:=f->quo(f,gcdex(f,p,c),c);
> sys2:={ seq(pp(op(i,gb)),i=1..nops(gb)) };
Для sys2 также вычисляем базис Гребнера и факторизуем первый полином:
> gb2:=Groebner[Basis](sys2,plex(a,b,c,d));
> nops(gb2);
6
> factor(op(1,gb2));
(8*d+3)*(432*d^2+18*d-83)*(56*d^2-63*d+18)*(1152*d^5-144*d^4+1488*d^3-80*d^2+612*d-27)
Hетрудно проверить (методом Штурма), что все множители, за исключением третьего, имеют действительные корни.
Будем последовательно добавлять каждый из множителей к нашему базису gb2.
С полиномом 8*d+3 все получается тривиально:
> gb3:=factor( Groebner[Basis]( {op(gb2),8*d+3} ,plex(a,b,c,d) ) );
gb3 := [8*d+3, (c-1)^2, (c-1)*(b-1), (b-1)^2, a+b+c-3]
Этот случай неинтересен. Смотрим дальше:
> gb4:=factor( Groebner[Basis]( {op(gb2),432*d^2+18*d-83} ,plex(a,b,c,d) ) );
gb4 := [432*d^2+18*d-83, 11*c^2-294-72*c*d-51*c-648*d, 11*b*c+120+72*d*b+72*c*d+18*b+18*c+216*d, 11*b^2-294-72*d*b-51*b-648*d, a+b+c-3]
Чтобы оценить значение целевой функции, добавим еще одно полиномиальное уравнение и решаем:
> vp := simplify( numer(x-f(a,b,c)) );
> sol4:=[solve( { op(gb4), vp } )];
Смотрим на численные значения:
> for i to nops(sol4) do print(evalf(allvalues(op(i,sol4)))) od;
{c = -4.372281324, a = -4.372281324, d = .4179874245, x = -4.507924546, b = 11.74456265}, {b = .255437353, x = .757924546, d = -.4596540911, c = 1.372281324, a = 1.372281324}
{a = 11.74456265, b = -4.372281324, c = -4.372281324, d = .4179874245, x = -4.507924546}, {a = .255437353, b = 1.372281324, x = .757924546, d = -.4596540911, c = 1.372281324}
{b = -4.372281324, a = -4.372281324, d = .4179874245, x = -4.507924546, c = 11.74456265}, {b = 1.372281324, x = .757924546, d = -.4596540911, a = 1.372281324, c = .255437353}
Как видим, тут есть интересное значение целевой функции x = .757924546, смотрим чему оно соответствует:
> allvalues(op(1,sol4));
{c = -3/2-(1/2)*33^(1/2), a = -3/2-(1/2)*33^(1/2), d = -1/48+(11/144)*33^(1/2), x = -15/8-(11/24)*33^(1/2), b = 6+33^(1/2)}, {b = 6-33^(1/2), x = -15/8+(11/24)*33^(1/2), d = -1/48-(11/144)*33^(1/2), c = -3/2+(1/2)*33^(1/2), a = -3/2+(1/2)*33^(1/2)}
Вот и вылезли наши корешки из 33.
Остается последний случай:
> gb5:=factor( Groebner[Basis]( {op(gb2),1152*d^5-144*d^4+1488*d^3-80*d^2+612*d-27} ,plex(a,b,c,d) ) );
Hо тут численная проверка не дает интересных значений целевой функции.
Примерно так.
Max