![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
вторая задача олимпиады
Jul. 25th, 2021 01:52 amВторая задача Международной математической олимпиады в этом году оказалась одной из самых сложных - ее полностью решили всего 16 участников.
Мне кажется, что я ее решил, но мог проглядеть какую-то дырку в доказательстве - помогите мне и объясните, если так.
Само неравенство выглядит очень "естественным" и первая мысль - это что оно как-то легко должно сводиться к неравенству Коши-Шварца (Коши-Буняковского в русской традиции). Но ничего такого я не нашел. Вторая мысль - это что надо доказывать индукцией по числу переменных, рассматривая лишь "добавок", который вносит в обе суммы добавление x_n. Это очень заманчиво, но после разбора нескольких простых примеров становится ясным, что для "добавка" неравенство просто неверно иногда. То есть, если мы изолируем только слагаемые, в которых участвует x_n, может случиться, что сумма слева больше суммы справа - просто расстояние между значениями слева и справа для первых n-1 переменных между собой - еще больше, и "пересиливает".
Если есть доказательство, выводящее это неравенство из чего-то фундаментального, я это очень хочу знать. Но сам такого не нашел.
Дальше следует мое решение, если хотите решать сами, не читайте.
Идея 1. Если одно из чисел равно 0, его можно выбросить, и расстояние между левой и правой частью неравенства не изменится. Таким образом мы сведем задачу к меньшему числу переменных.
Идея 2. Если два числа противоположны друг другу, x и -x, то их оба можно выбросить, не изменив расстояние между левой и правой частью. Из-за симметрии члены, включающие эти x и -x, слева и справа оказываются одинаковыми (советую это проверить). Это тоже позволяет свести задачу к меньшему числу переменных.
Решение. Представим себе, что мы плавно двигаем все числа x_i одновременно, сдвигая их влево или вправо на одинаковое расстояние, т.е. прибавляя к ним всем одно и то же число x, положительное или отрицательное. Можно представить, как все числа x_i нанесены на бумагу и мы двигаем бумагу по числовой прямой. Что при этом происходит с неравенством? Левая часть вообще не меняется, потому что все x_i-x_j остаются теми же. Правая часть меняется. Если мы двигаем достаточно влево, все x_i+x_j становятся отрицательными и правая часть стремится к плюс бесконечности; если вправо, все x_i+x_j становятся положительными и опять стремится к плюс бесконечности. В середине же правая часть в каком-то месте получает наименьшее значение. Если мы докажем неравенство для этого места, то и в общем случае, понятно, оно будет верно, потому что левая часть не изменится, а правая только вырастет.
Представим, как мы двигаем числа слева направо от минус бесконечности. Поначалу все суммы x_i+x_j отрицательны, и наше движение вправо уменьшает правую часть. В какой-то момент какое-то x_i+x_j пересекает барьер 0, и после этого модуль заставляет нас брать квадратный корень не из -x_i-x_j, как до сих пор, а от x_i+x_j. В любой данный момент есть "отрицательные" пары, с x_i+x_j меньше нуля, и "положительные". Движение вправо уменьшает вклад от отрицательных пар (по модулю они уменьшаются) и увеличивает - от положительных. Плюс на "барьерах" отрицательные проходят через 0 и становятся положительными. Рано или поздно значение функции начинает расти, а не уменьшаться. Для наглядности мы можем заменить каждый x_i+x_j на константу a_ij, и рассматривать правую часть как фукнцию от переменной x, которую мы добавляем к каждой a_ij: сумма по всем i,j от sqrt(|x + a_ij|). По мере роста x "отрицательные" слагаемые x+a_ij превращаются в "положительные".
Возьмем тот x, для которого вся сумма получает наименьшее возможное значение. Я утверждаю, что это происходит на "барьере", в тот момент, когда одно из слагаемых равно 0. Это логично, потому что именно на барьерах слагаемые превращаются из уменьшающихся при росте x в увеличивающиеся. Предположим на секунду, что это действительно так - что из этого следует? Если мы опять вернемся к исходным числам x_i,x_j, и посмотрим, как они выглядят после сдвига, то "барьер" как раз означает, что x_i+x_j=0. При этом если i=j, то это случай, когда одно из чисел 0, а если это два разных числа, то они противоположны. В обоих случаях мы можем свести задачу к меньшему числу переменных, выбросив эти одно или два числа, и значит индукцией по числу переменных мы завершили доказательство.
Осталось строго доказать, что наименьшее значение функция принимает именно на "барьере". Почему это обязано быть так? Рассмотрим ситуацию между барьерами. По мере увеличения x у нас некоторые слагаемые - "отрицательные" - равны sqrt(-x-a_ij) и убывают, некоторые - "положительные" - равны sqrt(x+a_ij) и возрастают. Может, именно тут в какой-то момент возрастающие слагаемые "превозмогают" убывающие, и общая сумма теперь будет только расти? Я думаю, что нет, и мой аргумент основан на том, что функция sqrt(x+epsilon)-sqrt(x) монотонно убывает для фиксированного epsilon (проверяется вычислением ее производной по x). Если при каком-то x функция получила минимум, то на x+epsilon возрастающие слагаемые в сумме выросли больше, чем убывающие уменьшились. Но тогда при движении от x-epsilon к x возрастающие слагаемые должны были увеличиться еще чуть больше, а убывающие уменьшиться еще чуть меньше. Выходит, что на x-epsilon значение функции должно быть еще меньше, и это противоречие. Поэтому минимум должен достигаться в одной из точек перелома - "барьере".
Мне кажется, что я ее решил, но мог проглядеть какую-то дырку в доказательстве - помогите мне и объясните, если так.
Само неравенство выглядит очень "естественным" и первая мысль - это что оно как-то легко должно сводиться к неравенству Коши-Шварца (Коши-Буняковского в русской традиции). Но ничего такого я не нашел. Вторая мысль - это что надо доказывать индукцией по числу переменных, рассматривая лишь "добавок", который вносит в обе суммы добавление x_n. Это очень заманчиво, но после разбора нескольких простых примеров становится ясным, что для "добавка" неравенство просто неверно иногда. То есть, если мы изолируем только слагаемые, в которых участвует x_n, может случиться, что сумма слева больше суммы справа - просто расстояние между значениями слева и справа для первых n-1 переменных между собой - еще больше, и "пересиливает".
Если есть доказательство, выводящее это неравенство из чего-то фундаментального, я это очень хочу знать. Но сам такого не нашел.
Дальше следует мое решение, если хотите решать сами, не читайте.
Идея 1. Если одно из чисел равно 0, его можно выбросить, и расстояние между левой и правой частью неравенства не изменится. Таким образом мы сведем задачу к меньшему числу переменных.
Идея 2. Если два числа противоположны друг другу, x и -x, то их оба можно выбросить, не изменив расстояние между левой и правой частью. Из-за симметрии члены, включающие эти x и -x, слева и справа оказываются одинаковыми (советую это проверить). Это тоже позволяет свести задачу к меньшему числу переменных.
Решение. Представим себе, что мы плавно двигаем все числа x_i одновременно, сдвигая их влево или вправо на одинаковое расстояние, т.е. прибавляя к ним всем одно и то же число x, положительное или отрицательное. Можно представить, как все числа x_i нанесены на бумагу и мы двигаем бумагу по числовой прямой. Что при этом происходит с неравенством? Левая часть вообще не меняется, потому что все x_i-x_j остаются теми же. Правая часть меняется. Если мы двигаем достаточно влево, все x_i+x_j становятся отрицательными и правая часть стремится к плюс бесконечности; если вправо, все x_i+x_j становятся положительными и опять стремится к плюс бесконечности. В середине же правая часть в каком-то месте получает наименьшее значение. Если мы докажем неравенство для этого места, то и в общем случае, понятно, оно будет верно, потому что левая часть не изменится, а правая только вырастет.
Представим, как мы двигаем числа слева направо от минус бесконечности. Поначалу все суммы x_i+x_j отрицательны, и наше движение вправо уменьшает правую часть. В какой-то момент какое-то x_i+x_j пересекает барьер 0, и после этого модуль заставляет нас брать квадратный корень не из -x_i-x_j, как до сих пор, а от x_i+x_j. В любой данный момент есть "отрицательные" пары, с x_i+x_j меньше нуля, и "положительные". Движение вправо уменьшает вклад от отрицательных пар (по модулю они уменьшаются) и увеличивает - от положительных. Плюс на "барьерах" отрицательные проходят через 0 и становятся положительными. Рано или поздно значение функции начинает расти, а не уменьшаться. Для наглядности мы можем заменить каждый x_i+x_j на константу a_ij, и рассматривать правую часть как фукнцию от переменной x, которую мы добавляем к каждой a_ij: сумма по всем i,j от sqrt(|x + a_ij|). По мере роста x "отрицательные" слагаемые x+a_ij превращаются в "положительные".
Возьмем тот x, для которого вся сумма получает наименьшее возможное значение. Я утверждаю, что это происходит на "барьере", в тот момент, когда одно из слагаемых равно 0. Это логично, потому что именно на барьерах слагаемые превращаются из уменьшающихся при росте x в увеличивающиеся. Предположим на секунду, что это действительно так - что из этого следует? Если мы опять вернемся к исходным числам x_i,x_j, и посмотрим, как они выглядят после сдвига, то "барьер" как раз означает, что x_i+x_j=0. При этом если i=j, то это случай, когда одно из чисел 0, а если это два разных числа, то они противоположны. В обоих случаях мы можем свести задачу к меньшему числу переменных, выбросив эти одно или два числа, и значит индукцией по числу переменных мы завершили доказательство.
Осталось строго доказать, что наименьшее значение функция принимает именно на "барьере". Почему это обязано быть так? Рассмотрим ситуацию между барьерами. По мере увеличения x у нас некоторые слагаемые - "отрицательные" - равны sqrt(-x-a_ij) и убывают, некоторые - "положительные" - равны sqrt(x+a_ij) и возрастают. Может, именно тут в какой-то момент возрастающие слагаемые "превозмогают" убывающие, и общая сумма теперь будет только расти? Я думаю, что нет, и мой аргумент основан на том, что функция sqrt(x+epsilon)-sqrt(x) монотонно убывает для фиксированного epsilon (проверяется вычислением ее производной по x). Если при каком-то x функция получила минимум, то на x+epsilon возрастающие слагаемые в сумме выросли больше, чем убывающие уменьшились. Но тогда при движении от x-epsilon к x возрастающие слагаемые должны были увеличиться еще чуть больше, а убывающие уменьшиться еще чуть меньше. Выходит, что на x-epsilon значение функции должно быть еще меньше, и это противоречие. Поэтому минимум должен достигаться в одной из точек перелома - "барьере".
