Wednesday, April 13, 2011

The Infinite Hotel

This story is a follow-up to The Highest Number.

David Hilbert had worked hard for it, but after what seemed like an eternity, his Grand Hotel was finally completed. So many people had been involved in building it, it was impossible to keep count. But there it was, up and running, with more guests coming in every day. And Hilbert's Grand Hotel was grand alright. You see, this hypothetical hotel had an infinite amount of rooms. A feature Hilbert was keen to advertise: “The hotel that always has a room available!

Business was good. Hilbert enjoyed his tasks as manager, as quirky situations tend to occur a lot in a hotel with infinitely many rooms. Such a situation often required a mind-bending solution, just the kind of challenge Hilbert liked. And with the hotel quickly filling up, things were about to get crazy.

Take that first time the hotel was completely full. All rooms had been taken, there was not a single one left. And no guests were scheduled to check out anytime soon. Yet Hilbert didn't stop advertising about his vacant rooms. No, he had it all planned out. When he said there would always be a room available, he meant it.

So when a new guest arrived the next day, he knew exactly what to do. “Worry not,” Hilbert told him, “I'll simply move all existing guests to the next room. So the guests in room 1 to room 2, the guests in room 2 to room 3, and so on. This will free up room 1 for you.”
“But what about the people in the last room?” the new guest asked. Hilbert smiled. “What last room? We do not have one, the rooms go on forever. There is no problem!”

For the next few days, Hilbert repeated this procedure whenever new guests arrived. If more than one room was needed, he simply moved the existing guests that many rooms up. At some point a massive party arrived, needing 40,000 rooms. By moving the guests 40,000 rooms up, the hotel could easily deal with it. It was infinite, after all.

This went on for some time, until another challenge presented itself. An immense number of people arrived, all at the same time. An infinite amount of guests in fact, and they all needed a room.
Hilbert wondered what to do. “I cannot move the existing guests an infinite amount of rooms up, that's too vague. They will need a proper room number to go to,” he thought to himself. It didn't take him long to find a solution. He moved all existing guests to double their room number. The guests in room 1 to room 2, the guests in room 2 to room 4, room 3 to room 6, and so on. All existing guests thus occupied the even numbers. With half of the hotel now vacant, the new guests could occupy the odd numbers.

This too continued for a while. Despite many check-ins and check-outs, Hilbert was always able to make room. Weird situations still occurred.
One particular day, by pure coincidence, all the guests in the odd numbered rooms checked out. The hotel had been full before, so now only the guests in all the even numbered rooms were left. Hilbert figured a full hotel looked more alluring than one that was half empty, so he asked them all to move to the room numbered half their current room number. The hotel was now full again, even though no new guests had checked in.
Another day, all guests in room numbers above quadrillion checked out, leaving ‘only’ a quadrillion guests left. So on both these days the hotel had been completely full, the same number of guests had checked out (namely, infinitely many), yet a different number of guests remained (infinitely many vs. a quadrillion). Just another of the strange things Hilbert loved about the place.

Then business really got off the ground. People were coming in with coach-loads at a time. Hilbert would never forget the biggest challenge he had to face to date. Infinitely many coaches, containing infinitely many guests each. The double-room-number trick could not be applied here; that would only take care of one of the buses. Yet there were still an infinite amount more that he had to find a room for! Luckily for the guests, Hilbert had an affinity for mathematics and this problem too, he managed to solve.

First he once again moved all existing guests to the even room numbers. He then told the guests from bus 1 to calculate powers of 3 using their seat number. The result (3, 9, 27, 81, 243, …) was their room number. The guests in bus 2 he told to use powers of 5 (5, 25, 125, …), bus 3 was to use powers of 7, and each successive bus was to use the next prime number (11, 13, 17, 19, 23, 29, 31, 37, …). This ‘algorithm’ ensured that the same room would never come up twice.
When everyone was taken care of, Hilbert was amused to note that there were also an infinite amount of rooms still empty. Having to find rooms for the infinitely many coaches with infinitely many guests each, actually managed to free up an infinitely many extra rooms. Yep, it was a quirky hotel for sure.

Last I heard, the hotel was still doing great. Although somebody was making plans of building an even bigger one... but that's a story better saved for another post.

No comments:

Post a Comment