Добро пожаловать в Гран-отель Гранина! Он бесконечно лучше, чем Гранд-отель Гильберта.
- В нашем отеле вас почти не беспокоят, в отличие от отеля Гильберта, в котором гостей то и дело переселяют в другие номера.
- Мы принимаем даже автобусы с несчетным количеством гостей, от которых отказались в отеле Гильберта.
Как работает наш отель
➤ В нашем отеле, как и в отеле Гильберта, ∞ количество номеров: 0й, 1й, 2й, 3й… Когда в отеле заканчиваются номера, мы также принимаем гостей. Но в отличие от отеля Гильберта, у нас другой алгоритм. Каждый новый гость при регистрации выбирает случайное число ℕ от 0 до ∞. Это будет его номер. Наш гость может воспользоваться нашим внутренним мгновенным метро, чтобы добраться до своего номера. По прибытии, гость предлагает прежнему постояльцу выбрать случайное число 𝕄 от ℕ+1 до ∞ и переселиться туда, повторяя процедуру с прежним постояльцем. Вероятно, к каждому кто-нибудь постучится, но вряд ли это будет так уж скоро, так что наши постояльцы могут рассчитывать на длительный отдых.
➤ Бывают, конечно, и очень капризные гости, чьи имена состоят из бесконечного числа символов.
: ABBABABAABABBB…
: ABAAAABBBABBBB…
: BBBABABBBABBBB…
Эти гости непременно хотят, чтобы их комнаты как-то соответстовали их именам, и очень возмущаются, если их заселять по рандомному алгоритму. Но и на этот случай мы знаем что делать. Пусть имена состоят из “0” и “1” (а если нет, – возможно перевести любое имя бинарный вид). Каждому капризному гостю мы выдаем стартовый индекс 𝕂=1. Именно столько первых цифр своего имени гость считает за номер в гостинице. Если имя “1011”, гость с индексом 𝕂=1 отрпавляется в комнату 1 в двоичной и десятеричной системе исчисления. В случае если номер занят обычным посетителем, то тот переселяется в следующий случайный номер по обычному алгоритму. Если прежний постоялец – это капризный гость, он увеличивает свой индекс 𝕂 на 1 и пересчитывает номер. Для гостя “1011” с индексом 𝕂=2 новая комната должна быть 10 в двоичной системе, 2 в десятеричной. Таким образом, мы даже капризным гостям находим уголок в нашем отеле.
Мы, конечно, понимаем, что неспособны разместить всех капризных гостей. Но у нас один вход в отель, одна стойка регистрации и один консьерж. Сколько бы гостей ни прибыло, они будут проходить регистрацию по одному, и пусть они сами между собой решают, кто за кем стоит.
Заселим не всех, но каждого!


