олимипиадная задачка
Aug. 14th, 2014 10:26 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЯ заглянул в блог Тима Гауэрса - британского математика, лауреата премии Филдса, известного также своим блогом и книгами по математике для широкой публики. Увидел там любопытную запись за прошлый месяц, в которой Гауэрс решает "в реальном времени" одну из задач международной математической олимпиады (ММО) за этот год. То есть, он подробно записывает все свои мысли по мере решения задачи, предлагая таким образом читателю весь процесс решения. До того, как читать все это, он советует попробовать решить самому.
Мне эта идея понравилась, и я решил попробовать решить задачу и записать свои мысли до того, как прочитаю решение Гауэрса. К моему удивлению, решить получилось довольно быстро, минут за 15. Гауэрс упоминает, впрочем, что это первая задача, а первые задачи обычно полегче. Теперь я поступлю так же, как Гауэрс: посоветую вам решить самостоятельно, а потом уже смотреть на мое решение (или Гауэрса).
Задача: дана бесконечная последовательность целых положительных чисел a0 < a1 < a2 < ... Доказать, что существует единственное n≥1, так, что an<(a0+a1+...+an)/n≤an+1.
Дальше я постараюсь рассказать, как ее решал, а потом пойду посмотрю, что записал Гауерс. Если вы хотите сохранить чистоту эксперимента, сначала докажите сами, обратите внимание (или запишите) на последовательность ваших мыслей, а потом читайте дальше.
Я решил вначале посмотреть, что происходит с какой-то простой последовательностью, и выбрал 1 < 3 < 5 < 7...
На бумаге у меня это записано так:
a0=1
a1=3
a2=5
a3=7
(a0+a1)/1 = 4
(a0+a1+a2)/2 = 4.5
(a0+...+a3)/3 = 5 1/3
Тут я ошибся, потому что невнимательно смотрел на индексы, и решил, что правильный ответ здесь n=2, т.к. 4.5 лежит между a1=3 и a2=5. На самом деле это неверно, потому что 4.5 должно лежать между a2 и a3: надо все время помнить тут, что между an и an+1 должно лежать среднее арифметическое первых n+1 членов, а не n - из-за этого "a0". Я сразу отметил это обстоятельство и сказал себе, что надо не путаться, но все равно в конкретном примере запутался. Правильный ответ здесь n=1, потому что уже среднее арифметическое первых двух, 4, лежит между a1 и a2.
(замечание, добавленное позже для прояснения: конечно, неверно называть это "средним арифметическим", потому что это сумма n+1 чисел, деленная на n; но в уме я тем не менее именно так его называл, отметив для себя при этом эту разницу и стараясь за ней следить)
Но несмотря на эту ошибку, стало интуитивно понятно, почему утверждение верно: члены последовательности "убегают" вдаль, а среднее арифметическое от них отстает. Тогда я решил проверить, насколько увеличивается среднее арифметическое в сравнении с членами последовательности при переходе к следующему n. Попытка прикинуть на бумаге сразу убедила меня, что сравнивать лучше, умножив всё на n:
n*an < a0+a1+...+an ≤ n*an+1
Я хочу доказать, что для какого-то n, и только для одного, это неравенство верно. Если мое интуитивное представление о том, что члены "убегают" от среднего арифметического верно, то логично попробовать доказать, что когда оно неравенство выполняется для n, оно не выполняется для n+1 и далее. Предположим, для n неравенство верно, т.е. средняя часть лежит между левой и правой. Мне бы хотелось доказать, что уже для n+1 левая часть обгонит среднюю, и дальше будет только отдаляться. Верно ли это? При переходе к n+1 средняя часть увеличивается на an+1, а левая часть из n*an становится (n+1)*an+1 = n*an+1 + an+1. Действительно левая часть увеличилась больше, чем средняя, и разница в их увеличении равна n*(an+1-an). И так будет всегда для любого n - то есть, как только левая обгонит среднюю, средняя уже никогда не обгонит ее обратно. Как доказать, что уже при переходе от n к n+1 левая обгонит среднюю? Мы знаем, что средняя между левой и правой, а расстояние между ними равно именно n*(an+1-an). Все сходится! Левая часть увеличивается в сравнении с средней на расстояние, дальше которого средняя не может отстоять от левой. В самом крайнем случае, когда средняя сейчас равна правой, при переходе к n+1 она станет равна левой и неравенство нарушится (потому что между левой и средней оно строгое); а если средняя меньше правой, то тем более.
Значит, я знаю, что как только средняя часть в первый раз попадает в сэндвич между левой и правой, этот первый раз получается единственный, дальше они от средней убегают. Кажется, я почти доказал. Нужно проверить еще две вещи. Во-первых, что с самого начала действительно левая меньше средней. Да, это так: для n=1 мы получаем 1*a1 < a0+a1. Тут, записывая это, я замечаю, что неправильно все делал в примере выше, и исправляю его для себя, убеждаюсь, что все все равно работает. Значит, вначале средняя больше левой; если она уже меньше правой, то все готово, если нет, то по мере роста n левая и правая части обгоняют среднюю, и как только она попадает в сэндвич между ними, это и есть наше единственное n. Но обязана ли она попасть между ними? Мне еще нужно доказать, что не может быть такого, что для n средняя часть больше левой и правой, а для n+1 уже меньше обеих - она их перепрыгнула. Если это невозможно, то доказательство окончено. Почему это невозможно?
Я как раз отошел от бумаги (помогаю купать ребенка), поэтому не хочу оперировать формулами в голове, легко ошибиться, поэтому пробую построить другой пример, с числами чуть побольше, чтобы легче видеть промежутки, и посмотреть, не могу ли я заставить среднюю часть перепрыгнуть. Пусть a0=10, a1=... ну скажем 20, тогда чтобы не было сразу решения при n=1, a0+a1=30 должно быть больше моей правой части a2. Возьмем a_2=26 например; при n=1 у нас левая-средняя-правая части неравенства вышли 20-30-26. Хорошо, теперь к n=2 левая часть стала 2*26=52, средняя 10+20+26=56, нет, средняя не перепрыгнула через левую. Чтобы правая 2*a3 осталась меньше левой надо брать a3=27, иначе не выйдет. Тут я начал запутываться с индексами при вычислении в уме, решил, что в целом выглядит убедительно, что средняя не перепрыгнет, и общая идея верна, и вернулся к бумаге.
Так, предположим, что при переходе от n к n+1 средняя перепрыгнула через левую и правую, тогда "неестественное" состояние, это что для n+1 средняя часть меньше левой, это максимум "неестественной" информации, которую я могу получить (потому что тогда меньше правой автоматически), пора это записать: (n+1)*an+1 ≥ a0+a1+...+an+1. Сокращаем an+1, присматриваемся... а, ну все понятно, это же эквивалентно условию того, что для n средняя часть меньше правой: a0+a1+...+an ≤ n*an+1. Кажется, я все доказал. Средняя часть не может перепрыгнуть интервал между левой и правой, не встав в него, потому что если она для n+1 встала слева от левой, то уже для n была слева от правой. Продумываю в голове все шаги еще раз... да, вроде все верно.
Это была наиболее подробная реконструкция мыслительного процесса, которую я смог организовать, пользуясь записанными на бумаге расчетами и памятью о том, как думал. Задача кажется подозрительно легкой для ММО (впрочем, я никогда не участвовал в ММО); мне кажется, что в олимипиадной ситуации, заранее настроившись и не отвлекаясь на домашние дела, она щелкается заметно быстрее, чем те 15 минут, что у меня заняло.
Теперь пойду посмотрю, что там Гауэрс настрочил.
Мне эта идея понравилась, и я решил попробовать решить задачу и записать свои мысли до того, как прочитаю решение Гауэрса. К моему удивлению, решить получилось довольно быстро, минут за 15. Гауэрс упоминает, впрочем, что это первая задача, а первые задачи обычно полегче. Теперь я поступлю так же, как Гауэрс: посоветую вам решить самостоятельно, а потом уже смотреть на мое решение (или Гауэрса).
Задача: дана бесконечная последовательность целых положительных чисел a0 < a1 < a2 < ... Доказать, что существует единственное n≥1, так, что an<(a0+a1+...+an)/n≤an+1.
Дальше я постараюсь рассказать, как ее решал, а потом пойду посмотрю, что записал Гауерс. Если вы хотите сохранить чистоту эксперимента, сначала докажите сами, обратите внимание (или запишите) на последовательность ваших мыслей, а потом читайте дальше.
Я решил вначале посмотреть, что происходит с какой-то простой последовательностью, и выбрал 1 < 3 < 5 < 7...
На бумаге у меня это записано так:
a0=1
a1=3
a2=5
a3=7
(a0+a1)/1 = 4
(a0+a1+a2)/2 = 4.5
(a0+...+a3)/3 = 5 1/3
Тут я ошибся, потому что невнимательно смотрел на индексы, и решил, что правильный ответ здесь n=2, т.к. 4.5 лежит между a1=3 и a2=5. На самом деле это неверно, потому что 4.5 должно лежать между a2 и a3: надо все время помнить тут, что между an и an+1 должно лежать среднее арифметическое первых n+1 членов, а не n - из-за этого "a0". Я сразу отметил это обстоятельство и сказал себе, что надо не путаться, но все равно в конкретном примере запутался. Правильный ответ здесь n=1, потому что уже среднее арифметическое первых двух, 4, лежит между a1 и a2.
(замечание, добавленное позже для прояснения: конечно, неверно называть это "средним арифметическим", потому что это сумма n+1 чисел, деленная на n; но в уме я тем не менее именно так его называл, отметив для себя при этом эту разницу и стараясь за ней следить)
Но несмотря на эту ошибку, стало интуитивно понятно, почему утверждение верно: члены последовательности "убегают" вдаль, а среднее арифметическое от них отстает. Тогда я решил проверить, насколько увеличивается среднее арифметическое в сравнении с членами последовательности при переходе к следующему n. Попытка прикинуть на бумаге сразу убедила меня, что сравнивать лучше, умножив всё на n:
n*an < a0+a1+...+an ≤ n*an+1
Я хочу доказать, что для какого-то n, и только для одного, это неравенство верно. Если мое интуитивное представление о том, что члены "убегают" от среднего арифметического верно, то логично попробовать доказать, что когда оно неравенство выполняется для n, оно не выполняется для n+1 и далее. Предположим, для n неравенство верно, т.е. средняя часть лежит между левой и правой. Мне бы хотелось доказать, что уже для n+1 левая часть обгонит среднюю, и дальше будет только отдаляться. Верно ли это? При переходе к n+1 средняя часть увеличивается на an+1, а левая часть из n*an становится (n+1)*an+1 = n*an+1 + an+1. Действительно левая часть увеличилась больше, чем средняя, и разница в их увеличении равна n*(an+1-an). И так будет всегда для любого n - то есть, как только левая обгонит среднюю, средняя уже никогда не обгонит ее обратно. Как доказать, что уже при переходе от n к n+1 левая обгонит среднюю? Мы знаем, что средняя между левой и правой, а расстояние между ними равно именно n*(an+1-an). Все сходится! Левая часть увеличивается в сравнении с средней на расстояние, дальше которого средняя не может отстоять от левой. В самом крайнем случае, когда средняя сейчас равна правой, при переходе к n+1 она станет равна левой и неравенство нарушится (потому что между левой и средней оно строгое); а если средняя меньше правой, то тем более.
Значит, я знаю, что как только средняя часть в первый раз попадает в сэндвич между левой и правой, этот первый раз получается единственный, дальше они от средней убегают. Кажется, я почти доказал. Нужно проверить еще две вещи. Во-первых, что с самого начала действительно левая меньше средней. Да, это так: для n=1 мы получаем 1*a1 < a0+a1. Тут, записывая это, я замечаю, что неправильно все делал в примере выше, и исправляю его для себя, убеждаюсь, что все все равно работает. Значит, вначале средняя больше левой; если она уже меньше правой, то все готово, если нет, то по мере роста n левая и правая части обгоняют среднюю, и как только она попадает в сэндвич между ними, это и есть наше единственное n. Но обязана ли она попасть между ними? Мне еще нужно доказать, что не может быть такого, что для n средняя часть больше левой и правой, а для n+1 уже меньше обеих - она их перепрыгнула. Если это невозможно, то доказательство окончено. Почему это невозможно?
Я как раз отошел от бумаги (помогаю купать ребенка), поэтому не хочу оперировать формулами в голове, легко ошибиться, поэтому пробую построить другой пример, с числами чуть побольше, чтобы легче видеть промежутки, и посмотреть, не могу ли я заставить среднюю часть перепрыгнуть. Пусть a0=10, a1=... ну скажем 20, тогда чтобы не было сразу решения при n=1, a0+a1=30 должно быть больше моей правой части a2. Возьмем a_2=26 например; при n=1 у нас левая-средняя-правая части неравенства вышли 20-30-26. Хорошо, теперь к n=2 левая часть стала 2*26=52, средняя 10+20+26=56, нет, средняя не перепрыгнула через левую. Чтобы правая 2*a3 осталась меньше левой надо брать a3=27, иначе не выйдет. Тут я начал запутываться с индексами при вычислении в уме, решил, что в целом выглядит убедительно, что средняя не перепрыгнет, и общая идея верна, и вернулся к бумаге.
Так, предположим, что при переходе от n к n+1 средняя перепрыгнула через левую и правую, тогда "неестественное" состояние, это что для n+1 средняя часть меньше левой, это максимум "неестественной" информации, которую я могу получить (потому что тогда меньше правой автоматически), пора это записать: (n+1)*an+1 ≥ a0+a1+...+an+1. Сокращаем an+1, присматриваемся... а, ну все понятно, это же эквивалентно условию того, что для n средняя часть меньше правой: a0+a1+...+an ≤ n*an+1. Кажется, я все доказал. Средняя часть не может перепрыгнуть интервал между левой и правой, не встав в него, потому что если она для n+1 встала слева от левой, то уже для n была слева от правой. Продумываю в голове все шаги еще раз... да, вроде все верно.
Это была наиболее подробная реконструкция мыслительного процесса, которую я смог организовать, пользуясь записанными на бумаге расчетами и памятью о том, как думал. Задача кажется подозрительно легкой для ММО (впрочем, я никогда не участвовал в ММО); мне кажется, что в олимипиадной ситуации, заранее настроившись и не отвлекаясь на домашние дела, она щелкается заметно быстрее, чем те 15 минут, что у меня заняло.
Теперь пойду посмотрю, что там Гауэрс настрочил.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
прошу прощения -
Date: 2014-08-14 07:32 pm (UTC)Re: прошу прощения -
Date: 2014-08-14 07:36 pm (UTC)Re: прошу прощения -
Date: 2014-08-14 08:14 pm (UTC)Re: прошу прощения -
Date: 2014-08-14 08:15 pm (UTC)Re: прошу прощения -
Date: 2014-08-14 08:19 pm (UTC)no subject
Date: 2014-08-14 07:56 pm (UTC)no subject
Date: 2014-08-14 08:01 pm (UTC)Для британского учоного и кодера с Израиля пыхтеть часами.
no subject
Date: 2014-08-14 08:10 pm (UTC)no subject
Date: 2014-08-19 01:17 pm (UTC)И вообще, г-н Задорнов, перелогинтесь.
no subject
Date: 2014-08-15 01:02 am (UTC)no subject
Date: 2014-08-14 08:23 pm (UTC)no subject
Date: 2014-08-14 08:25 pm (UTC)1) обозначим a_0+...+a_n за B_n, a a_n * n за A_n (это приходит в голову, когда смотришь на первое неравенство, получается A_n < B_n). Но тогда оказывается, что и второе чудесным образом вписывается, получается B_n <= A_(n+1) - a_(n+1), то есть B_(n+1) <= A_(n+1)
Получаем такое условие: A_n < B_n, но A_(n+1) >= B_(n+1)
2) Это сразу заставляет желать, чтобы A_n - B_n возрастало для всех n.
И действительно:
(A_(n+1)-A_n) - (B_(n+1)-B_n) = ((n+1)a_(n+1) - na_n) - a_(n+1) = n (a_(n+1) - a_n) > 0
UPD Ну да, не просто возрастало, но монотонно стремилось к бесконечности, что, конечно, выполнено.
no subject
Date: 2014-08-14 08:52 pm (UTC)что-то не понял
n*an < a0+a1+...+an ≤ n*an+1
вычтем n*an : слева 0, а справа отрицательное число a0-an + a1-an + ... где an>любого предыдущего члена
то есть n*an < a0+a1+...+an неверно
no subject
Date: 2014-08-14 08:55 pm (UTC)no subject
Date: 2014-08-14 09:37 pm (UTC)Излагаю ход своих мыслей. Выкладки делались на обратной стороне трёх кассовых чеков.
1) Проверим, для начала, так ли это — может, по дороге и на решение набредём. Пусть, скажем, an=n+1 — то есть, последовательность 1,2,3,... Тогда сумма посередине будет равна (n+1)(n+2)/2, а неравенство будет n+1 < (n+1)(n+2)/(2n) <= n+2. Первая часть переписывается как 2n<n+2, то есть n<2; вторая — как n+1<=2n, т.е., n>=1. Значит, такое n и правда есть, и оно равно 1. Хм. Общей закономерности не видно. Роем дальше.
2) Неограниченная сумма посередине действует мне на нервы. Можно ли переписать в более приятном виде? Ну, если эту самую сумму обозначить через bn, то an=bn-bn-1, и всё, действительно, переписывается. Так, погодите, а условие на возрастание an как запишется? А, это выпуклость последовательности bn: 2bn<bn-1+bn+1.
Ладно, как же теперь записывается то, что надо доказать? Вот как:
bn-bn-1 < bn/n <= bn+1-bn
OK, это слишком сложно. Надо, как минимум, домножить всё это на n, чтобы иметь дело только с целыми числами, и привести подобные, причём в каждой части отдельно.
Получаем из первой части
nbn-nbn-1 < bn
(n-1)bn < nbn-1
а из второй части
bn <= nbn+1-nbn
(n+1)bn <= nbn+1
Здесь я начал было делить первую часть на n-1, а вторую на n+1, чтобы записать более простое неравенство на bn, но вовремя остановился. Я вдруг понял, что делить надо ещё и на n, и тогда получится замечательно:
bn/n < bn-1/(n-1)
bn/n <= bn+1/(n+1)
О! А ведь это просто значит, что в последовательности bn/n нашёлся своего рода локальный минимум: значение, которое строго меньше предыдущего и нестрого — последующего.
Гипотеза первая: у этой последовательности есть ГЛОБАЛЬНЫЙ минимум — возможно, продолжающийся на несколько значений подряд.
Гипотеза вторая: эта последовательность (bn/n) САМА ЯВЛЯЕТСЯ ВЫПУКЛОЙ. Тогда первая гипотеза получится сразу.
Попробуем это доказать. Нам нужно установить, что 2bn/n <= bn-1/(n-1) + bn+1/(n+1). Мы уже знаем, что bn меньше чего-то похожего; попробуем этим воспользоваться. Тогда нужно показать, что
bn-1/n + bn+1/n <= bn-1/(n-1) + bn+1/(n+1).
Приводя подобные, получаем
bn+1/(n(n+1)) <= bn-1/(n(n-1))
bn+1/(n+1) <= bn-1/(n-1)
Хм... то есть, эта последовательность в таком случае должна быть убывающей. Как-то это непохоже на правду.
Тут у меня кончился первый чек, так что я сделаю передышку.
no subject
Date: 2014-08-14 09:51 pm (UTC)2bn <= bn-1/(n-1) + bn+1/(n+1).
Приводя к общему знаменателю, получаем
2(n2-1)bn <= (n2+n)bn-1 + (n2-n)bn+1.
Условие выпуклости говорит нам, что bn+1 >= 2bn-bn-1. Подставляя, получаем, что теперь нам нужно доказать следующее:
2(n2-1)bn <= (n2+n)bn-1 + 2(n2-n)bn - (n2-n)bn-1.
Приводя подобные, получаем
2(n-1)bn <= 2nbn-1
и тут я уже визуально опознал, что опять эта последовательность получается убывающей, что опять-таки сомнительно.
Поэтому я отбросил вторую гипотезу и стал думать над первой. Хм... Может быть, если представить, что в какой-то момент последовательность bn/n перестала идти вниз... кстати, а она шла вниз? Ах, да, ведь b0/0 — это плюс бесконечность, а следующий элемент последовательности вполне себе конечен... так вот, если в какой-то момент она перестала идти вниз, то дальше она не сможет снова пойти вниз? Так... допустим, что для какого-то n имеет место
bn/n >= bn-1/(n-1)
Сможем ли мы доказать подобное неравенство для n+1? Посмотрим, исходя из выпуклости
bn+1/(n+1) >= bn/n
следует из
(2bn-bn-1)/(n+1) >= bn/n
что эквивалентно
2nbn-nbn-1 >= (n+1)bn
что эквивалентно
(n-1)bn >= nbn-1
что эквивалентно
bn/n >= bn-1/(n-1)
а это у нас уже есть. Ееее!
no subject
Date: 2014-08-14 10:04 pm (UTC)Тут я довольно долго тупил. Ходил по комнате, ничего не записывая, стараясь понять, что тогда будет. Ничего не придумал, решил попробовать действовать от противного, и, для начала, записать, что в таком случае нам известно про последовательность bn:
I. bn+1 > bn
II. 2bn < bn-1+bn+1
III. bn+1/(n+1) < bn/n
Тут меня осенило. Мы ведь только что из того, что неравенство III неверно для n выводили, что оно неверно и для n+1. Может, получится какая-то оценка того, НАСКОЛЬКО это неравенство верно?
Я обозначил bn/n-bn+1/(n+1)=cn и принялся считать:
cn <
bn/n - (2bn-bn-1)/(n+1) =
[1/(n(n+1))] ((n+1)bn - 2nbn+nbn-1) =
[1/(n(n+1))] (nbn-1-(n-1)bn) =
[(n(n-1))/(n(n+1))] cn-1 =
cn-1(n-1)/(n+1).
М-м-м... что-то не видно, почему это не может быть всегда положительным.
Я приуныл, взял третий чек (второй кончился) и переписал на него:
I. bn+1 > bn
II. 2bn < bn-1+bn+1
и тут до меня дошло: ведь я не зря всё время старался избавляться от знаменателей! Перепишем третье условие так:
III. nbn+1 < (n+1)bn
А вот теперь никто не мешает нам положить
cn = (n+1)bn - nbn+1 <
(n+1)bn - n(2bn - bn-1) =
nbn-1 - (n-1)bn = cn-1
То есть, эта последовательность — cn — СТРОГО УБЫВАЮЩАЯ! А так как в этом варианте она ещё и целочисленная, то она не может всегда быть положительной. Значит, условие III не может выполняться. Ура!
no subject
Date: 2014-08-14 10:05 pm (UTC)no subject
Date: 2014-08-14 10:19 pm (UTC)Во-первых, это, оказывается, не задачи за ЭТОТ год. Это задачи за 2012 год.
Во-вторых, оказывается, проводилось это дело в курортном городе Мар-дель-Плата, в Аргентине. Я был в Мар-дель-Плате в 1997 году. На Международной Математической Олимпиаде! Уехал с серебряной медалью.
no subject
Date: 2014-08-14 10:22 pm (UTC)no subject
Date: 2014-08-14 10:24 pm (UTC)no subject
Date: 2014-08-14 10:03 pm (UTC)no subject
Date: 2014-08-15 12:12 am (UTC)Но про технику решения "в формате блога" хочу сказать много хорошего. Для меня это самый мощный (и самый медленный) метод решения задач (системное администрирование). Когда нифига не понятно, и масштаб проблемы не понятен, и не известно "как оно должно выглядеть в рабочем виде", и даже не понятно, туда ли смотришь, и есть ли проблема (точнее, правильно ли проблема сформулирована, или есть расхождение между ожиданиями и тем, как технология работает) - блог в корпоративной вики - это самое-самое важное.
Потому что туда можно и нужно выписывать все найденные по теме вещи, тупиковые пути, гипотезы, фрагменты текущего состояния (логов и т.д.) - и иногда, после того, как проблема решится, может оказаться, что это было две проблемы рядом - и записки о прошлом процессе оказываются очень и очень полезны. Особенно полезны через пол-года или год, когда снова сталкиваешься с "чем-то похожим" и страница позволяет сэкономить несколько часов агрессивной отладки, просто показывая готовое дерево размышлений и давая шаблоны для сравнения "так же или нет".
no subject
Date: 2014-08-15 08:15 am (UTC)Какое-то условие про числа. Давайте для наглядности нарисуем картинку: отметим целые точки с координатами (i, a_i). Если это первая задача с ММО, у неё может быть простое графическое решение.
Нарисовал так пять точек, посмотрел. Что-то не то: первая координата вообще на рисунке бесполезная, и со средним арифметическим трудно работать.
Может быть, стоит ввести новые переменные? Есть две идеи: частичные разности и частичные суммы. Суммы кажутся более приятными, тем более, что в неравенстве посередине они и стоят.
Нарисуем новую картинку, отметив точки с координатами (i, a_1 + a_2 + ... + a_i). Что тогда получается? Если взять любую из отмеченных точек, то тагенс наклона прямой, проведённой к ней из точки (0,0) это и будет средний член. А в левой и правой частях неравенства стоят теперь какие-то частичные разности.
Некоторая медитация показывает, что это -- тангенсы углов наклона отрезочков, соединяющих i-ю отмеченную точку c (i-1)-й и (i+1)-й.
Тогда первое неравенство значит то, прямая, идущая из (0,0), ниже первого отрезочка и выше второго? Нет, не так. Ниже обоих отрезочков, то есть она локально "касается" этой конструкции.
Понятно, что такие точки найдутся, но почему их одна? Тут я вспомнил, что числа из условия задачи строго возрастают, то есть каждый следующий из маленьких кусочков ломаной "круче" предыдущего. А это аналог того, что у непрерывной функции производная возрастает, значит, она выпукла. А в нашем случае точки по-аналогии образуют вершины выпуклого бесконечноугольника, понятно, что точка (0,0) снаружи и что из неё проходит к нему ровно одна касательная.
no subject
Date: 2014-08-15 10:54 am (UTC)no subject
Date: 2014-08-15 08:46 pm (UTC)no subject
Date: 2014-08-15 10:24 am (UTC)Пусть - разность
Тогда
...
Сумма
Исходное утверждение которое надо доказать - переписывается вот так:
Умножаем обе части на n:
вычитаем из всех трёх частей — самую левую.
Видим, что все bi тут входят в выражение как bi⋅i, поэтому выгодно переобозначить все bi⋅i как ci
Что мы видим: есть положительное число , из него вычитают положительные числа, значит эти суммы — уменьшаются. Будет один единственный момент, когда эта сумма перейдёт через 0, из неотрицательных чисел в отрицательные. Раз сумма перейдёт через 0 — значит как раз перед этим моментом будет выполнено условие «сумма меньше или равна очередного вычитаемого .
no subject
Date: 2014-08-15 06:05 pm (UTC)1b_1+...+(n-1)b_{n-1}< a_0<=1b_1+...+nb_n
или
с_{n-1}< a_0<=с_n
Последовательность с_n возрастает от с_0=0 и пересечет границу a_0>0 в единственной точке.