Как доказывать олимпиадные неравенства

На семинаре координаторов олимпиады "Кенгуру" Вячеслав Андреевич Ясинский прочёл лекцию о том, как можно доказывать олимпиадные симметричные неравенства с помощью собственного метода разностей переменных.

Действительно, на математических олимпиадах часто встречаются задания на доказательство неравенств, как, например, такое, с Международной олимпиады по математике 2001 года: $\frac{a}{\sqrt{a^2+8bc}}+\frac{b}{\sqrt{b^2+8ac}}+\frac{c}{\sqrt{c^2+8ab}}\geq 1$ (для положительных a,b,c).

Обычно чтобы доказать олимпиадное неравенство, его нужно привести к одному из базовых: Коши, Коши-Буняковского, Йенсена, неравенству между средними и т.д. Причём часто приходится пробовать различные варианты базового неравенства до достижения успеха.

Однако часто у олимпиадных неравенств (как у приведённого выше) есть одна особенность. При перестановке переменных (например, замене a на b, b на c и  c на a) они не изменятся.

Если функция нескольких переменных не меняется при любой их перестановке, то она называется симметрической. Для симметрической функции f от трёх переменных выполняется равенство:
f(x,y,z)= f(x,z,y)= f(y,x,z)= f(y,z,x)= f(z,x,y)= f(z,y,x)

Если же функция не меняется только при циклической перестановке переменных, она называется циклической.
f(x,y,z)= f(y,z,x)= f(z,x,y)

Для неравенств, которые строятся на основе симметрических функций, Вячеслав Андреевич разработал универсальный метод доказательства.
Метод состоит из следующих шагов.
1. Преобразовать неравенство так, чтобы слева оказался симметрический многочлен (обозначим его D), а справа 0.

2. Выразить симметрический многочлен D от переменных a, b, c через базовые симметрические многочлены.

Базовых симметрических многочленов от трёх переменных существует три. Это:
p = a+b+c - сумма;
q = ab+bc+ac - сумма попарных произведений;
r = abc - произведение.

Любой симметрический многочлен можно выразить через базовые.

3. Поскольку многочлен D симметрический, можно, не нарушая общности, считать, что переменные a, b, c упорядочены так: $a\geq b\geq c$

4. Вводим два неотрицательных числа х и у, таки, что x = a-b, y = b-c.

5. Снова преобразовываем многочлен D, выражая p, q и r через c и x, y. Учитываем, что
b = y+c
a = (x+y)+c

Тогда
p = a+b+c = (x+2y)+3c
q = ab+bc+ac = 3c2+2(x+2y)c+(x+y)y
r = abc = (x+y)yc + (x+2y)c2+c3

Обратите внимание, что скобки в выражениях, содержащих x и y, мы не раскрываем.

6. Теперь рассматриваем многочлен D как многочен от с с коэффициентами, выражающимися через х и у. Учитывая неотрицательность коэффициентов оказывается несложно показать, что знак неравенства будет сохраняться для всех допустимых значений с.

Поясним этот метод на примерах.
Пример 1. Доказать неравенство:
$(a+b+c)^2\geq 3(ab+bc+ac)$

Доказательство
Так как неравенство симметрическое (не меняется при любой перестановке переменных a, b, c), то представим его как
$(a+b+c)^2 - 3(ab+bc+ac)\geq 0$

Выразим многочлен в левой части через базовые симметрические:
$p^2 - 3q\geq 0$

Так как многочлен симметрический, можно считать, не ограничивая общности, что $a\geq b\geq c$ и $x = a-b\geq 0$, $y = b-c\geq 0$.

Выразим левую часть через x, y и c, представив её как многочлен относительно с.
p2-3q = ((x+2y)+3c)2-3(3c2+2(x+2y)c+(x+y)y) = (x+2y)2+6(x+2y)c+9c2-9c2-6(x+2y)c-3(x+y)y

После приведения подобных получаем неравенство вообще не содержащее переменную с
$(x+2y)^2-3(x+y)y\geq 0$

Вот теперь можно раскрыть скобки
$x^2+4xy+4y^2-3xy-3y^2\geq 0$
$x^2+xy+y^2\geq 0$ - что является верным как для нотрицательных x, y, так и для любых.

Таким образом, неравенство доказано.

Пример 2 (с Британской математической олимпиады 1999 года)
Доказать, что $7(ab+bc+ac)\leq 2+9abc$ (для положительных чисел, если a+b+c = 1)

Доказательство
Прежде чем начать сводить всё в левую часть, обратим внимание, что степени частей неравенства у нас не сбалансированы. Если в примере 1 обе части неравенства были многосленами второй степени, то тут многочлен второй степени сравнивается с суммой многочленов нулевой и третьей. Использлуем то, что сумма a+b+c по условию равна 1 и домножим левую часть на единицу, а двойку из правой части - на единицу в кубе.

$7(ab+bc+ac)(a+b+c)\leq 2(a+b+c)^3+9abc$

Теперь перенесём всё влево и представим левую часть как симметричный многочkен от a, b, c:
$7(ab+bc+ac)(a+b+c)- 2(a+b+c)^3-9abc\leq 0$

Выразим левую чаcть через базовые симметрические многочлены:
$7qp- 2p^3-9r\leq 0$

Выразим левую часть через x, y и c, представив её как многочлен относительно с.
7qp- 2p3-9r = 7(3c2+2(x+2y)c+(x+y)y)((x+2y)+3c)-2((x+2y)+3c)3-9((x+y)yc + (x+2y)c2+c3) = 7 (3(x+2y)c2+2(x+2y)2c+(x+2y)(x+y)y+9c3+6(x+2y)c2+3(x+y)yс) - 2 ((x+2y)3+9(x+2y)2c+27(x+2y)c2+27c3) - 9((x+y)yc + (x+2y)c2+c3) = 21(x+2y)c2+14(x+2y)2c+7(x+2y)(x+y)y+63c3+42(x+2y)c2+21(x+y)yс-2(x+2y)3-18(x+2y)2c-54(x+2y)c2-54c3-9(x+y)yc -9(x+2y)c2-9c3

Главное - аккуратно и внимательно выполнять преобразования. Как сказал Вячеслав Андреевич, если он выполняет преобразования и его кто-то отвлекает, он выбрасывает листок с формулами и начинает заново.

Для удобства сведения подобных в заключительном многочлене они выделены разными цветами.

Все слагаемые с c3 уничтожатся: 63c3-54c3-9c3 = 0
Это же произойдёт и со второй степенью с: 21(x+2y)c2+42(x+2y)c2-54(x+2y)c2-9(x+2y)c2 = 0

Преобразуем слагаемые с первой степенью с: 14(x+2y)2c+21(x+y)yс-18(x+2y)2c-9(x+y)yc = -4(x+2y)2c+12(x+y)yс = (12(x+y)y - 4(x+2y)2)c = (12xy+12y2 - 4x2-16xy-16y2)c = (4x2-4xy-4y2)c = -4 (x2+xy+y2)c - это выражение никогда не будет положительным.

И свободные члены: 7(x+2y)(x+y)y-2(x+2y)3 = 7(x+2y)(xy+y2) - 2(x+2y)(x2+4xy+4y2) = (x+2y) (7xy+7y2-2x2-8xy-8y2) = - (x+2y)(2x2+xy+y2) - и это выражение тоже.

Таким образом, исходное неравенство будет выполняться всегда, а в равенство оно превратится только при условии равенства a=b=c.

На своей лекции Вячеслав Андреевич разобрал ещё много интересных примеров. Попробуйте и вы применить этот метод для доказательства олимпиадных неравенств. Возможно, он поможет добыть несокольо ценных баллов.

А закончим мы эту статью "любимой" фразой из книг по подготовке к олимпиадам. Доказательство первого приведённого в статье неравенства оставляем читателю :)

Комментариев нет :

Отправить комментарий