The rooms are numbered 1, 2, 3 and so on without end: after every room there is another. Each room has exactly one guest. Late in the evening one more guest arrives. The manager cannot throw anyone out or put two guests in one room, but can ask guests to move to other rooms. Can the newcomer get a room?
The manager announces: "Everyone, please move from room n to room n + 1." Nobody is left without a room, since every room has a next one, and room 1 becomes free. A full infinite hotel can take one more guest, an infinite bus and even infinitely many buses. But there are guests for whom there will never be a room.
The German mathematician David Hilbert made up this imaginary hotel to show how infinite sets differ from finite ones. No such hotel exists, but you can reason about it just as strictly as about an ordinary one.
The rooms are numbered 1, 2, 3, 4 and so on. The numbers never run out: after every room there is a next one, and there is no last room.
Every room has exactly one guest. There are no free rooms, and the sign on the door says "No vacancy".
Nobody can be thrown out, and two guests can't share a room. But the manager can announce one moving rule over the loudspeaker, such as "the guest from room n goes to room …", and all guests move at once.
One more guest arrives. Can the manager give them a room of their own so that every old guest still has a room of their own too?
"Full means full: there is no free room, so the new guest has nowhere to stay"
In an ordinary hotel that is so: the guest in the last room has nowhere to go. An infinite hotel has no last room, so everyone can shift up by one, and room 1 becomes free.
The hotel is full, there are infinitely many rooms, and nobody may be thrown out. Pick an answer before reading on.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
In an ordinary full hotel with 100 rooms a new guest won't fit: the guest in room 100 has nowhere to move. Is there such a "guest in the last room" in the infinite hotel?
Guests can't be thrown out, but they can be asked to move to other rooms, all at once. If everyone goes to another room, can some room become free while nobody is left without one?
Try the rule "from room n to room n + 1". Who will live in room 5 then? And in room 1?
Four evenings, and each time there are more guests. Pick a moving rule or type your own and announce it. The animation shows the first rooms of the corridor, and the check searches hundreds of thousands of guests for someone without a room or two in one. The "Break the rule" button tests your own rule.
Answer round 1 first: the game shows the answer.
Each guest tonight has an endless string of 0s and 1s instead of a name, and every possible string is a different guest. Make a list of who goes in which room. Click a digit to change it, or take a ready-made list.
There is no randomness here, so instead of a simulation the computer honestly checks a rule on the first N rooms and the first N guests: who ended up where, whether any room has two guests, whether any guest has no room. Next to it is the exact answer, found by reasoning about all guests at once. See where the two disagree.
Answer round 1 first: the check shows the answer.
A finite check is not a proof. The rule "old guests to n + 1000" passes the check on 1,000 rooms and breaks at room 1,001. And the rule "passengers one by one" works for any finite number of passengers; only the infinite bus leaves everyone without a room. A rule can be proved only by reasoning: showing who lives in each room m and that this guest is the only one.
"Full" and "no room" mean the same thing only when there are finitely many rooms. The whole puzzle rests on the fact that an endless corridor has no last room.
“In plain words” is hidden on all puzzles.
Picture a line of people that never ends. The command is "everyone one step forward": the first person takes the second's place, the second takes the third's, and so on. Nobody is left without a place, because there is always one more place ahead of everyone. And the first place becomes free.
This is not the whole explanation yet: it fits one guest or any finite number of guests. An infinite bus needs another trick, which is in the next cards.
Do the same in a 100-room hotel: the guest in room 99 goes to 100, and the guest in room 100 has nowhere to go. Whatever rule you pick, you can't put 101 people into 100 rooms one each. In the infinite hotel there is no such "guest in room 100": whoever you name has a next room.
If there are infinitely many passengers, shifting by one room won't help: the shifting would never end. Instead the guest from room n goes to room 2n. All old guests end up in even rooms, each in their own, and all the odd rooms 1, 3, 5, … become free. The passenger in seat s goes to room 2s − 1. Something odd comes out: there are "as many" even numbers as there are numbers.
“Rigorous” is hidden on all puzzles.
To check that a hall has as many chairs as people, you don't have to count: just seat everyone, one per chair, and see whether anything is left over. Mathematicians call such a pairing a bijection. For infinite sets it is the only honest way to compare size: two sets are equally large if they can be split into pairs with nothing left over.
A set that can be numbered 1, 2, 3, …, that is, put into Hilbert's hotel one per room, is called countable. The hotel's guests, the guests plus one, the guests plus a bus and even the guests plus infinitely many buses all form countable sets, so they fit.
Write everyone into a table: row 0 for the old guests, row b for bus b, a column for each seat number. The rows are endless, and there are endlessly many rows, so you can't go row by row: the first row would never end. But every diagonal is finite: 1 cell, then 2, then 3. Walk the diagonals and hand out rooms 1, 2, 3, … in turn. Every guest in the table gets their own room at some point.
One new guest: the old guests shift, the new one goes to room 1. Each room m ≥ 2 has exactly one occupant, the guest from room m − 1.
An infinite bus: even rooms for the old guests, odd ones for the passengers.
Infinitely many buses (b = 0 for the old guests, seats s = 1, 2, 3, …): the diagonal walk. Diagonal d = b + s − 1 has d + 1 cells, and 1 + 2 + … + d rooms are handed out before it.
Another well-known way: every number m ≥ 1 is written in exactly one way as a power of two times an odd number. Bus b gets rooms 2b, 3·2b, 5·2b, …
Sets A and B are the same size (equinumerous) if there is a bijection between them. A set is countable if it is equinumerous with the natural numbers ℕ.
“Deeper” is hidden on all puzzles.
Click the digits. The row under the table is built from the diagonal with every digit flipped. It differs from row 1 in the first digit, from row 2 in the second, from row k in the k-th. So it is in no room, whatever list you make. There are more endless strings of 0s and 1s than rooms: such a set is called uncountable.
Georg Cantor published this argument in 1891. He had proved that the real numbers are uncountable back in 1874, in a different way.
Hilbert told the hotel story in a popular lecture course on the infinite in Göttingen in the winter of 1924–1925. The notes were written up by his assistant, the physicist Lothar Nordheim. Hilbert has both one new guest (a shift by 1) and infinitely many new ones (room n → 2n), and next to the hotel the same example about an infinite ball, where every new lady finds a partner.
Hilbert himself never published the hotel. His notes appeared in print only in 2013, and the hotel was made widely known by the physicist George Gamow in his 1947 book "One Two Three… Infinity". The story was untangled by the historian of science Helge Kragh in a 2014 paper. At first he thought Gamow was the author; then, having learned of Hilbert's notes, he retracted that himself.
The hotel leads into three worlds. In mathematics it splits infinities into countable and uncountable: fractions fit, real numbers don't. In logic it shows that a part can be "as big as" the whole. And in practice the same diagonal trick proves that no program can check every program for hanging.
Mathematics
The fraction p/q sits in row p and column q, so the fractions form the same endless table as the buses. Walk it along the diagonals, skipping cells like 2/2 or 2/4: they are the same 1 and 1/2. Every positive fraction gets its own room. Zero and negative fractions fit too: 0 in room 1, then a fraction and minus that fraction in turn. So the rational numbers are countable, even though between any two of them there are endlessly many others.
That won't work with the real numbers. Write a number between 0 and 1 in binary: it is an endless string of 0s and 1s, like the names of the fourth evening's guests. Cantor's diagonal finds a number that is on no list. There is a small catch: some numbers have two expansions, such as 0.0111… = 0.1000…, but it is easy to get around. There are uncountably many real numbers, and no manager can house them.
Logic
Pick some of the room numbers, say only the squares 1, 4, 9, 16, … The guest from room n can go to room n·n, and all the guests fit into the square rooms alone, one each. Among the first 100 numbers only 10 are squares, and among the first million only a thousand. Yet there are enough of them to pair with all the numbers.
In 1638 Galileo, through his character Salviati in "Two New Sciences", noticed exactly this about squares and concluded that "greater", "less" and "equal" don't apply to infinite quantities. Mathematicians took another road: they kept "equal" in the sense of one-to-one pairs and accepted that a part can equal the whole. In 1888 Richard Dedekind even made it the definition: a set is infinite if it can be paired off with a part of itself. In a finite set a part is always smaller than the whole.
Practice
In the table the rows are programs, the columns are input numbers, and a cell says whether the program stops on that input or runs forever. The program "Opposite" looks at the diagonal and does the reverse: on input k it stops if program k runs forever on input k, and loops if that one stops. So "Opposite" differs from every program in the table on at least one input, like Cantor's string.
Now suppose someone wrote a checker that correctly says, for any program on any input, whether it will stop. Then "Opposite" could be written as an ordinary program: ask the checker and do the reverse. But all programs can be numbered, like guests, and "Opposite" would have its own number k. On input k it would have to both stop and not stop. So no such checker exists. This idea, taught today as the halting problem, goes back to Alan Turing's 1936 paper.
In practice it means that compilers, code analysers and antivirus tools always miss something: they either let some hangs through, sometimes raise false alarms, or set a time limit. A perfect checker is impossible not for lack of speed but because of logic.
In his Göttingen lectures in the winter of 1924–1925 Hilbert gave two examples: the hotel and a ball where all the gentlemen have already asked the ladies to dance, yet a new lady still finds a partner. He drew a social conclusion: in a world with infinitely many houses and occupants there would be no homeless.
On 4 June 1925 in Münster Hilbert repeated the ideas of those lectures in his address "On the Infinite", this time without the hotel. It holds his famous line that no one shall expel us from the paradise Cantor created for us. At the same time he said that the infinite is nowhere to be found in nature itself.
The earliest known printed mention of the hotel came not from Hilbert but from a calculus textbook by Otto Haupt and Georg Aumann. Without naming Hilbert, it asks how to fit infinitely many new guests into a full infinite hotel.
George Gamow retold the hotel in "One Two Three… Infinity" and in a footnote cited Richard Courant's "unpublished, and even never written" "Complete Collection of Hilbert Stories". Gamow worked in Göttingen in the summer of 1928 and probably heard the story there.
Three centuries before Hilbert, Galileo noticed that every number has its square, so there are "as many" squares as numbers, though most numbers are not squares. He decided that infinite quantities can't be compared. Cantor showed that they can, and that there are different infinities.
The notes of the 1924–1925 lectures were included in the volume "David Hilbert's Lectures on the Foundations of Arithmetics and Logic 1917–1933", edited by William Ewald and Wilfried Sieg. Only then did it become clear that the hotel really was Hilbert's.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
Is “For everyone” the right level for this puzzle?
Thank you! This helps set the levels right.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.