Ломаем спички, или Алиса в стране математических ошибок

Есть у меня любимый форум, посвящённый головоломкам. Недавно я наткнулся там на следующую задачу:

Сидел однажды Вася у себя на кухне и от нечего делать спички ломал. Поломал, поломал и задумался — чему равна вероятность того, что по крайней мере одна спичка будет переломана точно посередине? Запас спичек у Васи неограничен.

Я довольно быстро доказал, что вероятность этого события равна нулю. Гордый собой, я запостил решение и ответ, ожидая плюсика в карму. Оказалось, однако, что авторский ответ совсем другой: 1 — 1/e. Забегая вперёд, скажу, что этот ответ неверен.

Неправильные авторские решения — довольно частое явление в интернет-головоломках. И я ни за что не стал бы писать этот пост, если бы автором задачи, а также её неверного решения, не был британский логик и алгебраист Чарльз Л. Доджсон, более известный под псевдонимом Льюис Кэрролл.

Тривия

Все математики знают, что автор «Алисы в стране чудес» был математиком. Широко известна байка о том, что королева Виктория, прочитав обеих «Алис», пожелала ознакомиться с другими книгами автора и была очень удивлена, когда ей принесли трактаты по аналитической геометрии и линейной алгебре. Помимо этих фундаментальных областей Кэрролл увлекался математическими головоломками и прочими интересностями. В 1888 году он издал книгу «Математические курьёзы», а спустя пять лет — её продолжение «Полуночные задачи», из которого и была взята задача про спички (разумеется, в оригинале не фигурировал никакой Вася). Ещё через пять лет Чарльза Доджсона не стало.

Решение Кэрролла

Решение, выложенное на форуме, было изложено очень коряво. Приходилось скорее угадывать, что именно хотел сказать автор. Тогда я обратился к источнику — той самой книге «Полуночные задачи». Мне предстояло удивиться второй раз: мой форумный оппонент не переврал ни единого слова. Переведя с русского на русский, я получил примерно следующее:

Возьмём n спичек, каждую из них разделим n точками на n + 1 равных частей. Положим, что n нечётно, а спички могут ломаться только в отмеченных точках, причём в каждой — с равной вероятностью. Тогда вероятность сломать спичку не посередине равняется 1 — 1/n, вероятность не сломать посередине ни одну из n спичек равняется (1 — 1/n)ⁿ. Устремляя n в бесконечность, получаем 1/e. Соответственно, вероятность сломать точно посередине хотя бы одну спичку будет равна 1 — 1/e.

Почему это не работает?

В своём решении автор обошёлся единственной переменной n. На самом деле, у нас есть две переменных: количество спичек и число точек на каждой из них. Обозначим их как p и q соответственно. Тогда вероятность, что ни одна из p спичек не будет сломана в средней из q точек, равна F(p,q) = (1 — 1/q)^p. Когда мы устремляем p и q к бесконечности, F устремляется к искомой вероятности… или не устремляется?

Проблема в том, что функция двух переменных F не имеет предела в бесконечности. При этом, однако, мы можем получить некий предел, двигаясь к бесконечности по определённой траектории (в данном случае Кэрролл находит предел по траектории, описываемой уравнением p = q). Однако значение этого предела целиком и полностью зависит от траектории. К примеру, если мы будем отмечать n точек, но брать не n спичек, а 2n, то получим вероятность (1 — 1/n)²ⁿ, которая в пределе даёт 1/e².

Точно так же мы можем получить и 1/e³, и 1/e⁴², и даже 1/e²⁵⁶. Очевидно, что выбранный метод решения не подходит для данной задачи.

Глубже в дебри

Есть две фундаментальных причины, по которым этот предельный переход не помог и не мог помочь Кэрроллу решить задачу (по крайней мере, решить верно). Первая из них такова: отметив на отрезке конечное число точек, в пределе мы получим бесконечное, но счётное их множество. В то же время множество точек отрезка имеет мощность континуум, что является бесконечностью более высокого порядка. Это различие было установлено Георгом Кантором где-то в 70-х годах XIX века. Впрочем, в момент написания «Полуночных задач» канторовская теория множеств ещё не была тем фундаментом математического анализа, которым стала впоследствии, да и Кэрролл, по свидетельствам биографов, был «далёк от переднего края математической науки своего времени». Так или иначе, даже в пределе места возможного перелома оказываются лишь малым подмножеством точек спички.

Вторая причина заключается в том, что в начальном и предельном случае мы, по сути, имеем дело с разными вероятностными пространствами и разными определениями вероятности. Когда мы выбираем одну точку из n, это происходит в рамках дискретного вероятностного пространства, выбор же точки на отрезке — уже геометрическая вероятность. Даже если такой переход корректен, это нуждается в дополнительном обосновании.

Каков же правильный ответ?

Нуль, разумеется. Геометрическая вероятность попасть в отдельно взятую точку равна нулю, не попасть в неё — единице. Вероятность не попасть в неё ни разу за бесконечное число попыток равна единице в степени бесконечность, что, в свою очередь, равняется… единице? Не совсем. Это такая же неопределённость, как и нуль, делённый на нуль. Здесь потребуются более тонкие методы.

Впечатлительным не смотреть

Покажем, что для сколь угодно малого d вероятность P сломать хотя бы одну спичку пополам меньше d.

Найдём такое c, что 1 — d = e^c. Если быть точным, c = ln(1 — d). Пусть спички имеют единичную длину и пронумерованы. В середине первой спички закрасим отрезок длиной 1 — e^c/2, в середине второй — длиной 1 — e^c/4, в середине энного — длиной 1 — e^c/2ⁿ. Отметим, что c < 0, поэтому все указанные длины будут положительны.

Вероятность того, что ни одна спичка не будет разломлена в точке, принадлежащей закрашенному отрезку, равна e^c/2 * e^c/4 *… * e^c/2ⁿ *… = e^{(c/2 + c/4 +… + c/2ⁿ + …)} = e^c = 1 — d. Следовательно, вероятность того, что хотя бы один разлом попадёт в закрашенный отрезок, равна d. Поскольку если одна из спичек будет разломлена посередине, разлом придётся на закрашенный отрезок, мы можем заключить, что P < d.

Число d было выбрано произвольно. Значит, P меньше любого положительного числа, т.е. P = 0, ч.т.д.

На самом деле

Загадочная ошибка профессионального математика заинтриговала меня, и я решил найти оригинал книги. Помучив Гугл минут двадцать, мне удалось-таки добился желаемого. Что же я увидел?

Скан страниц

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

The chance of one failure is (n — 1)/n

Вероятность сломать спичку в одной точке равна (n — 1)/n

Во-вторых, часть доказательства из перевода в оригинале попросту отсутствовала! В частности, там даже не была указана величина 1 — 1/e. Кроме того, там имелась интересная пометка:

N.B. What follows here was NOT thought out.
Важная Заметка: Следующая часть не была тщательно продумана.

Всё это указывает на то, что «неправильное решение» Кэрролла было скорее черновиком, нежели завершённым рассуждением. По каким-то неведомым нам причинам он просто не смог уделить достаточного внимания этой задаче. Также по выкладкам заметно, что математический анализ не является областью специализации автора.

Прояснив таким образом беспокоивший меня вопрос, я сел писать свой первый пост на Хабр.

ссылка на оригинал статьи http://habrahabr.ru/post/167041/