Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

олимипиадная задачка

Я заглянул в блог Тима Гауэрса - британского математика, лауреата премии Филдса, известного также своим блогом и книгами по математике для широкой публики. Увидел там любопытную запись за прошлый месяц, в которой Гауэрс решает "в реальном времени" одну из задач международной математической олимпиады (ММО) за этот год. То есть, он подробно записывает все свои мысли по мере решения задачи, предлагая таким образом читателю весь процесс решения. До того, как читать все это, он советует попробовать решить самому.

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

Теперь пойду посмотрю, что там Гауэрс настрочил.
Tags: задачка, математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 28 comments