Парадокс «Гранд-отель»

Парадокс «Гранд-отель» — мысленный эксперимент, иллюстрирующий свойства бесконечных множеств. Он демонстрирует отель с бесконечным количеством комнат, в каждой из которых находится постоялец. При этом в гостиницу всегда можно подселить ещё посетителей, даже если их бесконечное множество. Впервые парадокс был сформулирован немецким математиком Давидом Гильбертом в 1924 году и популяризирован в книге Георгия Гамова «Раз, два, три… бесконечность» в 1947 году.

Парадокс

Гость ω приходит в отель, в котором все комнаты заняты. Для того чтобы освободить ему комнату, гость из комнаты 1 переходит в комнату 2, гость из комнаты 2 — в комнату 3 и так далее. И новый гость ω селится в комнате 1.

Представьте себе отель со счётным множеством комнат, в каждой из которых находится постоялец. На первый взгляд, в отель невозможно подселить новых посетителей, как если бы речь шла об обычной гостинице, с конечным количеством комнат.

Новый посетитель

Для того чтобы подселить нового человека, нам придётся освободить одну комнату. Для этого мы переселим гостя из комнаты № 1 в комнату № 2, гость из комнаты № 2 перейдёт в комнату № 3 и так далее. В общем случае, гость из комнаты n переселится в комнату n+1. Таким образом, мы освободим первую комнату, в которую можно будет поселить нового гостя.

Бесконечное количество новых посетителей

В этом случае нам придётся освободить бесконечное количество комнат: постояльца из комнаты 1 переселим в комнату 2, из комнаты 2 в комнату 4, в общем случае из комнаты n переселим в комнату 2n. Таким образом мы освободим все нечётные комнаты, количество которых также счётное множество.

Бесконечное количество автобусов с бесконечным количеством пассажиров

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

Метод степени простого числа

Для начала, переселим всех постояльцев из своих комнат в комнаты степени 2. Таким образом, человек из комнаты $i$ теперь будет в комнате $2^{i}$. Всех пассажиров из первого автобуса поселим в комнаты под номером $3^{n}$, из второго автобуса в комнаты под номером $5^{n}$. Пассажиров из автобуса $c$ поселим в комнаты $p^{n}$, где $p$ — $c$-ное нечётное простое число. Согласно основной теореме арифметики (см. статью Основная теорема арифметики) номера совпадать не будут. Это решение оставляет свободными комнаты, номера которых не являются степенью простого числа, то есть, большинство непростых чисел: 6, 10, 12, 14, 15, 18, 20, 21, 22 и т. д.

Метод факторизации целых чисел

Каждого гостя, который сидит на месте $n$ в автобусе $c$, можно поселить в комнате $2^{n}3^{c}$ (отель можно обозначить как нулевой автобус). К примеру, гость из комнаты 2592 ($2^{5}\times 3^{4}$) находился в 4 автобусе и сидел на 5 месте. Так как каждое число имеет единственное разложение в произведение простых множителей, ни один из гостей не останется без комнаты и никто не будет поселён в занятую комнату. Как и в предыдущем методе, в этом случае остаются свободные комнаты.

Метод чередования

Для каждого гостя сравниваются длины номеров его автобуса и места в какой-либо позиционной системе счисления. Если одно из чисел короче, к нему добавляются ведущие нули, пока оба числа не будут иметь одинаковое количество цифр. Чередуя цифры этих чисел, получим номер комнаты. Например, пассажир на сидении 6917 в автобусе 843 получит комнату номер 60981473, то есть 60981473.

В отличие от решения со степенями простых чисел, метод чередования заполняет отель полностью, не оставляя пустых комнат.

Метод треугольного числа

В начале, каждый житель отеля будет переселён из комнаты $n$ в комнату $T_{n}$ (то есть $n$-ное треугольное число, ${\frac {n(n+1)}{2}}$). Далее, гости, которые сидят на месте $n$ в автобусе $c$ будут поселены в комнату $T_{c+n-1}+n$. Таким образом, все комнаты будут заселены, и в каждой комнате будет только один житель.

Высшие уровни бесконечности

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

Далее будет использоваться обозначение адреса пассажира в виде «место-автобус-паром». Например, 768-85-7252 — адрес пассажира на 768-ом месте в 85-ом автобусе на 7252-ом пароме.

Метод факторизации целых чисел можно применить, добавив новое простое число: пассажир, сидящий на месте $n$ в автобусе $c$ на пароме $f$, будет поселён в комнату $2^{n}3^{c}5^{f}$. Данный метод возвращает очень большие числа для небольших входных данных. Например, пассажир с адресом 10-45-26 займёт комнату 4507923441392263334111022949218750000000000 ($2^{10}\times 3^{45}\times 5^{26}$). Как было отмечено ранее, метод оставляет огромное количество комнат пустыми.

Метод чередования можно использовать, чередуя не по две цифры, а по три. Так, пассажир с адресом 1-2-3 займёт комнату 123, а пассажир с адресом 42609-233-7092 займёт комнату 400207620039932.

Предвидя возможность любого уровня бесконечности, администрация отеля пожелает назначать номера таким образом, чтобы жителям не нужно было переселяться при заселении новых гостей. Одним из возможных решений является присвоение гостям двоичного номера, где единицы разделяют группы нулей, в каждой группе количество нулей равно соответствующему числу из адреса гостя, для каждого уровня бесконечности. Например, гость с адресом 2-5-4-3-1 будет поселён в комнату 10010000010000100010, что соответствует десятичному числу 590882.

Как дополнение к этому методу, из каждой группы нулей удаляется один нуль. Таким образом, гость с адресом 2-5-4-3-1 будет заселён в комнату 101000010001001, что соответствует десятичному 10308. Это дополнение гарантирует, что каждая комната будет заселена гостями.

Анализ

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

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

См. также

• Парадокс удвоения шара
• Парадокс Галилея
• Принцип Дирихле (комбинаторика)