Путаница с ключами

Пусть число номеров и гостей конечно, обозначим его \(N\). Попробуйте выписать формулу для искомой вероятности в этом случае. Можно начать с \(N = 2{,}\ 3{,}\ \ldots\) и попробовать заметить некую закономерность. Затем можно будет взять предел при \(N\to\infty\).

Итак, предположим, что число комнат, ключей и математиков конечно и равно \(N\). Попробуем найти вероятность того, что в этом случае хотя бы один математик окажется в той комнате, которая была ему уготована изначально.

Обозначим через \(K_i\) событие, которое заключается в том, что стоящий \(i\)-м в очереди математик получил ключ от комнаты с номером \(i\) (то есть — ключ от своей комнаты). Поскольку нас устраивает, если случится хотя бы одно из событий \(K_i\) (\(i = 1,\ \ldots, N\)), то нужно посчитать вероятность объединения \(K_1\cup K_2 \cup \ldots \cup K_N\), которую мы обозначим \(\mathbb{P}(K_1\cup K_2 \cup \ldots \cup K_N)\). Важно помнить, что события \(K_i\) могут наступать одновременно (например, первый и второй в очереди могут получить ключи от своих комнат), то есть они не являются несовместными. А значит, эту вероятность нельзя вычислить как сумму вероятностей событий \(K_i\) по отдельности.

К счастью, есть сравнительно простой способ вычислить искомую вероятность. В этом нам поможет формула включений-исключений в ее вероятностном варианте:

Выглядит, может быть, не слишком приятно, но на самом деле, посчитать с ее помощью то, что нам нужно, уже довольно просто. Итак, согласно этой формуле, чтобы вычислить вероятность объединения нескольких событий, нужно взять сумму вероятностей этих событий по одному, вычесть сумму вероятностей всех попарных пересечений, прибавить сумму вероятностей пересечений по три, и так далее, продолжая чередовать знаки, пока не дойдем до вероятности пересечения всех событий (здесь уже даже сумма не нужна). Отметим, что во второй сумме мы берем все пары индексов \((i,\ j)\), в которых \(i\) и \(j\) пробегают значения от 1 до \(N\) и \(i<j\), — это делается для того, чтобы каждая пара учитывалась ровно один раз. Аналогично с тройными пересечениями и далее.

Давайте посмотрим, как устроены отдельные «части» этой формулы, и понадеемся, что мы сможем заметить какую-нибудь закономерность.

Первая «часть» — это сумма \(\sum\limits_{i=1}^N \mathbb{P}(K_i)\). Чему равна вероятность того, что ключ с номером \(i\) достался \(i\)-му в очереди? Поскольку сейчас нас не волнует, что случилось с другими ключами, то ответ на этот вопрос — \(\frac{1}{N}\). Чтобы в этом убедиться, можно представить, что вы случайным образом раскладываете \(N\) ключей на \(N\) мест, так что каждый ключ с равной вероятностью может оказаться на любом месте. Но тогда и каждое из мест может с равной вероятностью «получить» любой из ключей — в том числе и ключ с тем же номером, что и у этого места. В итоге эта сумма превращается в \(N\cdot\frac1N\), то есть она просто равна 1.

Теперь разберемся со второй «частью». В ней фигурируют вероятности попарных пересечений, \(\mathbb{P}(K_i\cap K_j)\). Все такие вероятности опять равны между собой и равны \(\frac1N\cdot\frac{1}{N-1}\), поскольку нам теперь нужно, чтобы два конкретных ключа достались конкретным математикам. Сколько таких пар существует? Ответ дается биномиальным коэффициентом \(C_N^2=\frac{N\cdot(N-1)}{2}\) (попробуйте объяснить себе, почему это так). Значит, вторая сумма превращается в \(C_N^2\cdot\frac1N\cdot \frac{1}{N-1}=\frac12.\)

Рассуждения для третьей «части» аналогичные. Вероятность того, что какие-то три конкретных ключа попадут к своим «законным владельцам», равна \(\mathbb{P}(K_i\cap K_j \cap K_k)=\frac1N\cdot\frac1{N-1}\cdot\frac1{N-2}\). Число таких троек равно \(C_N^3=\frac{N\cdot(N-1)\cdot(N-2)}{3!}\), поэтому эта «часть» дает вклад \(\frac1{3!}\) в общее дело.

Совершенно аналогично найдем, что вклад четвертой «части» равен \(\left(-\frac1{4!}\right)\), пятой — \(\frac1{5!}\) (здесь это тире, а не минус), и так далее. Последняя «часть» даст вклад \(\frac1{N!}\) с соответствующим знаком.

Итого, наша вероятность

Ответ на исходную задачу получается при предельном переходе \(N\to\infty\):

Можно было бы оставить его в таком виде, но оказывается, что эта бесконечная сумма равна вполне конкретному числу, которое мы сейчас найдем. Читатели, знакомые с основами математического анализа, вероятно, уже заметили, что наша сумма очень похожа на ряд Тейлора для экспоненты:

Если подставить \(x=-1\), то получим почти то, что требуется. Разница лишь в степени \(-1\) и в том, что суммирование начинается с нуля, а не с единицы. Но с этим легко справиться:

Отсюда получаем окончательный ответ:

Ответ в задаче вполне может показаться парадоксальным. Все-таки, 63% — это больше половины (и близко к 2/3). В то же время ясно, что есть бесконечно много способов так перемешать ключи, что никто из математиков точно не получит «свой» ключ. Например, можно любым способом разбить натуральный ряд на пары, и каждому дать ключ от другой комнаты из пары. Таких разбиений уже бесконечно много, а можно придумать сколько угодно других.

С математической точки зрения эта задача про поведение перестановок натурального ряда и вероятность наличия «неподвижной точки» в перестановке. «Обертка» про отель и математиков здесь использована скорее для красоты. Более известно использование этой «обертки» в другом контексте. Немецкий математик Давид Гильберт использовал аналогию с бесконечным отелем для иллюстрации кажущейся парадоксальной природы бесконечных множеств. Для широкой публики Гильберт известен прежде всего тем, что в 1900 году представил знаменитый список из 23 задач из разных областей, которые по его мнению представляли наибольшую значимость для математиков XX века. Некоторые из этих задач оказали сильнейшее влияние на развитие современной математики; на данный момент несколько проблем Гильберта все еще не решены ни в каком виде.

Теория множеств является одним из основных «языков» современной математики. Сейчас ее основы проходят школьники матклассов и участники математических кружков, но как полноценная часть математики она оформилась довольно поздно — лишь во второй половине XIX века, благодаря трудам Георга Кантора и ряда других математиков. При этом еще долгое время многие математики отказывались ее принимать, а многие другие пытались, наоборот, подвести под эту теорию прочный формальный «фундамент». Одна из причин всех этих сложностей в том, что без должной аккуратности, используя кажущиеся самоочевидными конструкции и логические переходы, очень легко построить «самопротиворечивые» множества или, что в данном случае то же самое, прийти к логическому парадоксу (см. парадоксы теории множеств). А математики не любят, когда в построениях возникают противоречия, — если только это не доказательство «от противного».

Один из самых известных таких парадоксов — парадокс брадобрея, являющийся одним из вариантов парадокса Рассела (на самом деле, они не эквивалентны, но не будем сейчас вдаваться в тонкости). Пусть в некой деревне живет брадобрей, который бреет всех жителей деревни, которые не бреются сами, и только их. Бреет ли этот брадобрей сам себя? Рассмотрим множество \(M\) всех тех, кого брадобрей бреет. Если он входит в это множество, то получается, что он бреет сам себя, а значит он не должен брить себя, то есть он не должен входить в множество \(M\). Теперь предположим, что наш брадобрей не входит в множество \(M\). Тогда получается, что он не бреется сам, а значит он должен себя брить, то он должен входить в множество \(M\). В обоих случаях получается противоречие — в этом и заключается парадокс. Разгадка здесь, конечно, в том, что такой брадобрей вовсе не обязан существовать. Парадокс Рассела так легко уже не решается.

Вернемся к Гильберту и его аналогии про отель (который иногда так и называют — «отелем Гильберта»). Все мы понимаем, что если в отеле конечное число номеров, то утверждения «все номера заняты» и «нельзя разместить еще одного гостя» равносильны (надеюсь, вы не оказывались в такой ситуации!). На языке множеств это означает, что между конечными множествами с разным числом элементов нет взаимно-однозначного соответствия (биекции). Для бесконечных множеств это не так. И чтобы проиллюстрировать это, Гильберт использовал свой «отель».

Итак, допустим, что участники математического конгресса, коих бесконечно много, расселились по номерам. на всякий случай оговорим, что мы здесь подразумеваем лишь счетные множества. Но тут приезжает еще один математик, про которого все забыли. Все номера заняты — казалось бы, разместить опоздавшего нет никакой возможности? Но находчивый управляющий придумывает такое решение: пусть каждый постоялец отеля переселится в следующий номер. Тогда самый первый номер освободится — туда и можно будет заселить опоздавшего. Это рассуждение показывает, что, грубо говоря, «бесконечность + 1» = «бесконечность». Аналогично можно справиться с любым конечным число опоздавших. Если количество опоздавших равно \(k\), то управляющий должен переселить постояльца комнаты с номером \(n\) в комнату c номером \(n+k\), — это высвободит первые \(k\) комнат, в которых можно будет разместить опоздавших.

А что делать, если опоздавших бесконечно много (но счетно)? Оказывается, есть способ разместить и их. Для этого переселим постояльцев по следующему правилу: постоялец из комнаты \(n\) переселяется в комнату с номером \(2n\). Тогда высвободятся все комнаты с нечетными номерами, и в них можно заселить опоздавших: математик номер \(m\) занимает комнату с номером \(2m-1\). Таким образом, первый из опоздавших попадет в комнату №1, второй — в комнату №3, третий — в комнату №5 и так далее. Ясно, что всем найдется место, а значит расселение можно считать успешным.

Переводя на язык множеств, мы получили, что объединение двух счетных множеств тоже является счетным множеством. Из этого следует, что и объединение любого конечного числа счетных множеств будет тоже счетным (попробуйте доказать это). А как быть с бесконечным «числом» счетных множеств? Оказывается, что и оно тоже явялется счетным. Показать это можно разными способами. Воспользуемся опять «отелем Гильберта».

Итак, у нас есть полностью заселенный отель с бесконечным числом номеров. Предположим, что на заселение прибыли новые математики, причем их привезли в бесконечном числе автобусов, а в каждом автобусе бесконечно много пассажиров. Удобно считать, что, во-первых, все автобусы пронумерованы, а во-вторых, места в каждом автобусе тоже пронумерованы от 1 до \(\infty\). Это допустимые предположения, поскольку мы договорилось, что множества счетные.

Сначала переселим всех нынешних постояльцев, так что обитатель комнаты с номером \(n\) отправится в комнату номер \(2^n\). Пассажиров первого автобуса расселим в комнаты, номера которых являются степенями тройки, пассажиров второго автобуса — в комнаты, номера которых являются степенями пятерки, и так далее. Продолжая использовать комнаты, номера которых являются степенями простых чисел, мы гарантируем, что коллизий не возникнет. А поскольку простых чисел бесконечно много, то и до каждого автобуса когда-нибудь дойдет очередь.

Этот способ не самый эффективный — комнаты, номера которых не являются степенями простых чисел (а также комната №1), не будут заселены. Если потребовать, чтобы по окончании заселения в отеле не осталось пустых комнат, то можно действовать, например, так, как показано на рисунке ниже. Сначала выселим всех постояльцев и выстроим их в ряд, который получит номер 1. Пассажиров из каждого автобуса высадим и тоже вытсроим по рядам, которые получат номера 2, 3, и т. д. Каждый ряд бесконечен только в одну сторону, то есть люди в нем тоже пронумерованы естественным образом. В итоге, каждому математику присвоена пара чисел — номер ряда и номер в этом ряду. Теперь пойдем «змейкой», начиная с (1, 1), как показано на рисунке. Ясно, что в каком ряду бы ни стоял человек и на каком месте он бы ни стоял, до него рано или поздно дойдет очередь. А значит, он получит свою комнату в отеле (в качестве упражения — выведите формулу, которая связывает номер комнаты с позицией \((m,\ n)\)). То есть все будут заселены. Важно помнить, что все, о чем мы здесь говорим — это мысленные эксперименты, и не нужно их прямо пытаться перенести в реальность. Вывод, который следует из этих построений, такой: счетное объединение счетных множеств тоже счетно. Такие вот удивительные свойства у бесконечных множеств. И мы затронули лишь счетные множества...

Нумерация «змейкой». В скобках указаны номера комнат, которые получат математики, стоящие на соответствующих местах в своих рядах. Рисунок с сайта cut-the-knot.org