August 14th, 2014

moose, transparent

ньютоновский мир

Два человека стоят рядом на краю крыши здания, в руках у них одинаковые футбольные мячи. Они одновременно бросают свои мячи с одинаковой силой, но один бросает свой мяч вниз, а другой - от себя, горизонтально. Какой из мячей первым коснется земли: тот, что бросили вниз, тот, что бросили горизонтально, или одновременно?

Этот вопрос в одном эксперименте был частью опросника, который задавали студентам американских университетов до и после их первого курса по физике (ньютоновская механика). Этот конкретный вопрос интересен тем, что обычно студенты отвечают на него (в среднем, по статистике) намного лучше до прохождения курса, чем после него.
moose, transparent

собаки лают, караван идет

Гуманитарная колонна из России вновь начала движение

14 мая 2096 года. Специальный корреспондент BBC-Космос передает с орбиты Нептуна, что обнаруженная там гуманитарная колонна из России вновь начала движение. "Спутниковые снимки показывают повреждения на трех последних КАМАЗах конвоя, и эти машины взяты на буксир другими КАМАЗами" - сообщает пресс-релиз НАСА - "но общее количество машин не уменьшилось со времен последнего наблюдения 26 лет назад".

Пресс-секретарь международной исследовательской базы на Нептуне Шейла Джонсон опровергла сообщения в некоторых СМИ, согласно которым конвой направлялся в город Первомайск на Нептуне. "Это полный вздор. На Нептуне нет никаких городов. Есть большой кратер неподалеку от нашей базы, некоторые российские участники экспедиции в шутку называют его Первомайским. Но это неофициальное название, на картах его нет. Официально это кратер Доброй Воли", заявила Джонсон.

Гуманитарный конвой движется в сторону границы с Украиной.
moose, transparent

вспомнить все

Есть десять доводов за то, чтобы учить английский язык, и только один против. Выучив язык, вы никогда уже не сможете услышать песни "битлов" так, как слышали их в детстве.

Я вот пытаюсь вспомнить про "Терминатор". Когда эти фильмы появилось, мы понимали - из фильма, или вообще откуда-то - что означает это слово, или это просто было какое-то название? Я теперь не могу это вспомнить, потому что знание языка полностью перекрыло то впечатление, которое когда-то было. Но я совершенно точно не знал в конце 80-х, что "to terminate" означает в том числе "убить", и что отсюда "Терминатор". Когда я смотрел в русском переводе первого и второго "Терминатора", то как я воспринимал это название робота? Это как-то объяснялось в переводе или было понятно из контекста - или если бы это называлось, не знаю, "Бунтематор", то ничего бы существенно не изменилось, и мы бы просто знали, что в фильме про робота-убийцу он называется Бунтематор и отсюда название фильма?

Не могу вспомнить.
moose, transparent

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

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

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

Теперь пойду посмотрю, что там Гауэрс настрочил.