It is the night before Tihar, and every hotel on the road is full. Late at night a tired trekker knocks at the door of a very strange one, Hotel Ananta. Its rooms are numbered 1, 2, 3, 4, … and they never end: for every room there is a next one. Tonight every single room has a guest in it.
“Sorry, we are full,” says the manager. But her daughter, who is in Grade 7, looks up from her homework. “We can give him a bed,” she says, “without sending anyone away and without putting two guests in one room.” The manager laughs. The trekker waits. Can she be right?
The rule of the hotel is that guests may be asked to move, as long as everyone moves at once, by the same rule, and everyone still ends up in a room of their own. Try some rules yourself.
Guess first. A full hotel with endless rooms, and one more guest arrives. What happens?
Pick an answer to see why.
Try it
One guest, then a few more
Here is the daughter’s rule for one new guest, written as a table. Every guest moves from room n to room n + 1.
| Guest was in room | 1 | 2 | 3 | 4 | 5 | … | 100 | … |
|---|---|---|---|---|---|---|---|---|
| Moves to room | 2 | 3 | 4 | 5 | 6 | … | 101 | … |
Check the two things the rule needs. Every guest gets a room: for any room number n, there is a room n + 1. No two guests share: two different guests started in different rooms, so after adding 1 they are still in different rooms. And one room is now empty, room 1, because nobody was in room 0 to move into it.
A bus that never ends
At midnight a bus pulls up that is as strange as the hotel. Its seats are numbered 1, 2, 3, … forever, and every seat has a passenger. Try it in the widget: choose An endless bus.
Moving everyone up by 40, or by a crore, frees only a fixed number of rooms, and the bus has more passengers than that. Whatever number you move by, the passenger in the next seat after it is left in the street. The daughter needs a rule that frees endless rooms at once.
Which rule for the guests already in the hotel leaves endless rooms empty?
Pick an answer to see why.
So the guests double their room numbers, and the passengers come in: seat 1 to room 1, seat 2 to room 3, seat 3 to room 5. In general, the passenger in seat k goes to room 2k − 1: seat 10 to room 19, seat 100 to room 199. Every passenger has a room, every old guest has a room, and nobody shares.
What’s going on
Counting without counting
How do you know a class has as many chairs as students, without counting either? Ask everyone to sit down. If every student has a chair and no chair is empty, there are just as many of each. You have matched them: each student with one chair, each chair with one student, nothing left over.
A matching like this, where every member of one set has exactly one partner in the other and nobody is left over on either side, is called a one-to-one correspondence. Counting is a matching too: when you count five mangoes, “one, two, three, four, five”, you match the mangoes one to one with the numbers 1 to 5. So for finite sets, two sets have the same number of members exactly when they can be matched one to one. You met that number in school as the cardinal number of a set, written n(A).
Why a full finite hotel really is full
Suppose a hotel has 100 rooms, all full, and a guest arrives. Every rule for moving the guests sends 100 guests into 100 rooms with nobody sharing, so the 100 rooms are still all taken: there is nowhere left for the 101st. Moving up by one would send the guest in room 100 to room 101, which doesn’t exist. A finite set can never be matched one to one with a part of itself that leaves something out.
The endless hotel did exactly that. Doubling matched all the guests with the even rooms, only part of the hotel, and nothing was left over. That is what makes it endless.
Galileo’s puzzle
Nearly 400 years ago, Galileo noticed the same thing with numbers. Every counting number has a square: 1 has 1, 2 has 4, 3 has 9, and so on. So the squares can be matched one to one with all the counting numbers. But the squares are only a small part of the numbers, and they get rarer: up to 100 there are 10 squares, up to 10,000 only 100, up to 10 lakh only 1,000.
So are there fewer squares than numbers, or just as many? Both answers feel right. Galileo decided that words like “equal”, “greater” and “less” simply don’t work for endless collections, only for finite ones.
More than two centuries later, Georg Cantor decided the other way. He said: let matching be the test, for endless sets as for finite ones. If two sets can be matched one to one, they are the same size, however strange that feels. Then the even numbers, the squares and all the counting numbers are the same size, as Figure 34.1 shows, and the hotel’s guests fit into the even rooms. A set that can be matched one to one with the counting numbers 1, 2, 3, … is called countably infinite (or just countable): you can list its members in a line, first, second, third, …, so that each one has its place somewhere in the list.
Which of these sets is not the same size as the counting numbers 1, 2, 3, …?
Pick an answer to see why.
Harder: endless buses
The next night is worse. Endless buses arrive: bus 1, bus 2, bus 3, … forever, and each one has endless seats, all full. How can the hotel fit them all?
To keep it tidy, the daughter first asks the guests already in the hotel to step outside and count themselves as one more busload. Now the job is to give a room to every passenger of every bus. Picture them as a grid, buses down the side and seats across, endless both ways. She needs to call the passengers one at a time, giving the first one called room 1, the next room 2, and so on, in an order that reaches every passenger in the end.
The obvious order fails. Bus by bus, the hotel gives rooms to bus 1’s passengers, seat 1, seat 2, seat 3, …, and since bus 1 never runs out, it never gets to bus 2 at all. Every room is used up by bus 1, and all the other buses wait forever.
The order that works runs along the diagonals of the grid. First bus 1, seat 1. Then the two passengers whose bus and seat numbers add up to 3: bus 1 seat 2, bus 2 seat 1. Then the three that add up to 4, and so on. Each diagonal is finite (the dth one has d passengers), so the list finishes every diagonal and moves on, and every passenger, whatever their bus and seat, lies on some diagonal and gets called after a finite wait:
| Room | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Bus, seat | 1, 1 | 1, 2 | 2, 1 | 1, 3 | 2, 2 | 3, 1 | 1, 4 | 2, 3 | 3, 2 | 4, 1 |
The diagonals end at rooms 1, 3, 6, 10, 15, 21, …, the triangle numbers from How Many Handshakes at a Party of 30?. So the room for bus b, seat s can be worked out without listing: it is on diagonal d = b + s − 1, the diagonals before it hold 1 + 2 + … + (d − 1) passengers, and within its diagonal it is the bth. The passenger in bus 4, seat 3 is on diagonal 6, after 1 + 2 + 3 + 4 + 5 = 15 others, fourth in line: room 19.
Fractions fit too
Here is a surprise from the same grid. Write the fraction b⁄s in the seat of bus b, seat s: 1⁄1, 1⁄2, 2⁄1, 1⁄3, 2⁄2, … Every positive fraction appears somewhere in the grid (3⁄4 is bus 3, seat 4), so walking the diagonals lists every positive fraction, skipping a fraction like 2⁄2 that is a repeat of 1⁄1. The fractions, which crowd so thickly that there are endless many between 0 and 1, are countable: there are just as many as there are counting numbers. Cantor proved this in 1873.
The twist: where the rules break
When guests leave
Arriving guests behave very well at Hotel Ananta. Leaving guests do not. Suppose the hotel is full, and endless guests check out. How many are left?
- Everyone in an odd room leaves. The guests in rooms 2, 4, 6, … stay: endless guests are left.
- Everyone in rooms 4 and above leaves. Only 3 guests are left.
- Everyone leaves. No guests are left.
Each time, endless guests left an endless hotel, and the answer was endless, or 3, or 0. So “infinity take away infinity” has no answer of its own: it depends on which guests leave. The same kind of trap caught the copy trick in Can You Add Halves Forever and Still Get One?, which gave −1 for a sum that has none.
A bus that will not fit
After all this, you might think every endless crowd fits into Hotel Ananta. Cantor showed in 1891 that it isn’t so, with a beautiful argument you can follow with a pencil.
Imagine a bus with one passenger for every endless string of 0s and 1s: 0101010…, 1111…, every possible one. Suppose someone claims to have fitted them all in. Write down the strings of the guests in rooms 1, 2, 3, … one under another. Here are the first five (each goes on forever):
| Room | Guest’s string |
|---|---|
| 1 | 01101… |
| 2 | 10100… |
| 3 | 11110… |
| 4 | 00010… |
| 5 | 10011… |
Now read the bold digits down the diagonal, 00111…, and flip each one, 0 to 1 and 1 to 0: 11000…. This new string differs from room 1’s guest in the 1st digit, from room 2’s in the 2nd, from room 3’s in the 3rd, and so on down the whole list: from every guest in some digit. So its passenger has no room, whatever list was made. These passengers can’t be matched with the counting numbers: there are more of them. Some infinities are bigger than others, which is the story of Are Some Infinities Bigger Than Others? in Math, Going Further, Grades 9–12 (coming soon). The endless decimals, like the strings, are one of the bigger infinities.
Hotel Ananta is empty, and a bus arrives with a passenger for every finite string of 0s and 1s: 0, 1, 00, 01, 10, 11, 000, …. Can they all get rooms?
Pick an answer to see why.
Where this is used
Questions
Hotel Ananta is full, and a family of 5 arrives. Which move for the guests already there gives the family exactly 5 empty rooms?
Pick an answer to see why.
Every guest of the full hotel doubles their room number, and an endless bus arrives. i. Which of rooms 1 to 10 are empty after the move? ii. Which room does the guest from room 7 move to? iii. Which room does the passenger in seat 6 get?
Hint
Answer
Which rule does not work for moving every guest of the full hotel?
Pick an answer to see why.
The guests of the full hotel move from room n to room 3 × n. Which rooms are empty now? How many endless buses could this make room for?
Hint
Answer
With the diagonal list of the endless buses (room 1 for bus 1 seat 1, room 2 for bus 1 seat 2, room 3 for bus 2 seat 1, …): i. Which room does bus 1, seat 10 get? ii. Which room does bus 10, seat 1 get? iii. Who is in room 20?
Hint
Answer
The whole numbers …, −3, −2, −1, 0, 1, 2, 3, … go on forever in both directions. Show that they still fit in Hotel Ananta, one number to a room. Which rooms do 10 and −10 get?
Hint
Answer
Use the grid of the endless buses, with the fraction b⁄s in bus b, seat s. i. Which room does 3⁄4 get on the diagonal list? ii. List the first ten fractions on the diagonals, leaving out repeats.
Hint
Answer
Where to go next
- Can You Add Halves Forever and Still Get One? The other side of infinity: adding endless pieces and getting a finite total.
- Is There a Biggest Prime Number? A proof that a set never ends: the primes go on forever.
- Is a Pattern That Works Ten Times Always True? Why checking many cases is not a proof about endless numbers.
- Are Some Infinities Bigger Than Others? (Grades 9–12) Cantor’s diagonal argument in full, for the decimals.
- What Is the Biggest Number a Computer Can Count To? (Computing, Going Further 6–8) A computer counts with a fixed number of digits, so unlike the hotel, it runs out.
- Grade 10, Review: sets and Venn diagrams: sets and their cardinal numbers n(A).
Where these facts come from
- Hilbert’s hotel: introduced in Hilbert’s lecture course of 1924–25, published only in 2013; popularized by George Gamow’s One Two Three… Infinity (1947); the moves n → n + 1, n → n + k, n → 2n, the endless coaches by pairing functions and by prime factors, 2⁵ × 3⁴ = 2,592 as seat 5 of coach 4: Wikipedia, “Hilbert’s paradox of the Grand Hotel”, read October 2026.
- Galileo’s Two New Sciences (1638), its speakers, Salviati’s conclusion that “equal”, “greater” and “less” are not applicable to infinite quantities, and Cantor’s matching view: Wikipedia, “Galileo’s paradox”, read October 2026.
- Countable sets defined by one-to-one correspondence with the natural numbers, the integers and rationals countable, Cantor’s 1874 proof that the reals are not and his 1891 diagonal argument, the diagonal (triangular) listing of pairs: Wikipedia, “Countable set”, read October 2026.
- Dedekind’s 1888 definition of an infinite set, and the squares as an example: Wikipedia, “Dedekind-infinite set”, read October 2026.
- Cantor’s dates and places (St Petersburg 1845, Halle 1918), the rationals and algebraic numbers countable in 1873, the reals not in 1874, Kronecker’s opposition: MacTutor, “Georg Cantor”, read October 2026.
- Hilbert’s birth in Königsberg (1862) and death in Göttingen (1943), his professorship at Göttingen from 1895 and defense of Cantor: Wikipedia, “David Hilbert”; the “paradise” sentence (“Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können”), from “Über das Unendliche”, Mathematische Annalen 95 (1926), the lecture given at Münster on 4 June 1925: Wikipedia, “Cantor’s paradise”, both read October 2026.
- The Bhagabati Sutra (about 300 BC) and “an enumerable, unenumerable or infinite number”, and the five kinds of infinity (as quoted from G. G. Joseph’s The Crest of the Peacock): MacTutor, “Jaina mathematics”, read October 2026.
- Bhaskara’s Bijaganita (Vija-ganita, Chapter I, §§ 15–16) on a quantity divided by zero, its name ananta-rási in Colebrooke’s note, and the quoted words: H. T. Colebrooke, Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bháscara (London, 1817; public domain), pp. 157–158, the Internet Archive’s scan; his dates (1114–1185) and that treating n/0 as a number leads to contradictions: MacTutor, “Bhaskara II”, both read October 2026.
- Brihadaranyaka Upanishad 5.1.1 in Devanagari and in Swami Madhavananda’s translation (1950), from which ours is made: Wisdom Library, “Brihadaranyaka Upanishad, verse 5.1.1”, read October 2026.
- Computable numbers introduced by Émile Borel in 1912, Turing’s 1936 paper, computable numbers countable and almost all real numbers not computable: Wikipedia, “Computable number”, read October 2026.
- Every number in this topic (the moves and the rooms they free, tested on the first 100,000 rooms; the squares up to 100, 10,000 and 10 lakh; the diagonal rooms and their inverse; 2,592; the whole numbers’ rooms; the fractions in diagonal order; the leaving guests; the flipped diagonal string and that it differs from every listed one) was computed in
checks/textbooks/math-further-6-8/34/tmp/hotel_numbers.pyand checked again by the reviewer’s own script,checks/textbooks/math-further-6-8/34/tmp/review/recheck.py.