Мне эта идея понравилась, и я решил попробовать решить задачу и записать свои мысли до того, как прочитаю решение Гауэрса. К моему удивлению, решить получилось довольно быстро, минут за 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 минут, что у меня заняло.
Теперь пойду посмотрю, что там Гауэрс настрочил.