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

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

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

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

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

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

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

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

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

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

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

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