Hilbert's hotel
Tonight's idea
Imagine a hotel with infinitely many rooms, numbered 1, 2, 3, and on forever. Tonight every room is full. A traveller arrives and asks for a room. In an ordinary full hotel, bad luck. In Hilbert's hotel the manager picks up the microphone: "Would every guest please move to the room one number higher." Room 1 moves to room 2, room 2 to room 3, and so on. Nobody is left without a room, because there is no last room to fall off the end of. Room 1 is now empty. The traveller checks in.
Later an infinite bus arrives carrying infinitely many passengers, numbered 1, 2, 3, … "Would every guest in room \(n\) please move to room \(2n\)." Now all the odd-numbered rooms are empty, and there are infinitely many of them. Passenger 1 takes room 1, passenger 2 takes room 3, passenger \(k\) takes room \(2k - 1\). Everyone fits.
This is the German mathematician David Hilbert's way of showing that infinity does not behave like a big number. Add one to infinity and you have the same infinity. Double it and you still have the same infinity. The even numbers 2, 4, 6, … can be paired up perfectly with all the whole numbers 1, 2, 3, …, each even number with its half, nothing left over on either side. So in the only sense that makes sense for infinite collections, there are exactly as many even numbers as whole numbers, even though the evens are only "half" of them.
The loop in this site's logo is the sign for that idea. Infinity is not a number you reach by counting very high. It is a different kind of thing, with its own rules, and the rules can be worked out. The same idea in a picture:
Watch one: is 0.999… really equal to 1?
Most people's gut says 0.999… (the 9s going on forever) is a tiny bit less than 1. The gut is wrong, and here is a proof you can do with a pencil.
Let \(x = 0.999\ldots\) Multiply both sides by 10: \(10x = 9.999\ldots\) Now subtract the first line from the second. On the left, \(10x - x = 9x\). On the right, the infinite tails of 9s cancel exactly, leaving \(9.999\ldots - 0.999\ldots = 9\). So \(9x = 9\), and \(x = 1\).
Still unconvinced? Ask what number would sit between 0.999… and 1. There is nowhere to put one. Two numbers with nothing between them are the same number. Or notice \(\tfrac13 = 0.333\ldots\), and multiply both sides by 3.
Your turn
- The hotel is full and one guest arrives. After the "move up one" announcement, where does the guest from room 7 end up? Where does the guest from room 1,000,000 end up? Is anyone homeless?
- The infinite bus arrives and everyone moves from room \(n\) to room \(2n\). Where does the guest from room 7 go? Which passenger from the bus gets room 15?
- Pair up the whole numbers 1, 2, 3, … with the multiples of 5 (5, 10, 15, …) so that nothing is left over on either side. Write the rule, and say which whole number is paired with 1,000.
- Use the same trick as the worked example to find what \(0.4999\ldots\) equals, and what \(0.272727\ldots\) equals as a fraction. (For the second one, multiply by 100 instead of 10.)
- Look at the square picture. Shade pieces of size \(\tfrac12, \tfrac14, \tfrac18, \tfrac1{16}\). What total have you shaded after those four? What is left unshaded? Write down what is left after \(n\) pieces, and explain why the leftover shrinks toward 0 but never reaches it at any single step.
- Two infinite buses arrive at the full hotel at once. Find a way to house everybody. (Hint: first clear out infinitely many rooms, then split those spare rooms into two infinite groups.)
Stretch: can every fraction get a room?
Write all the positive fractions in an infinite grid: row 1 has \(\tfrac11, \tfrac12, \tfrac13, \ldots\), row 2 has \(\tfrac21, \tfrac22, \tfrac23, \ldots\), and so on. Every fraction appears somewhere. Now walk a path that zig-zags through the grid along the diagonals, as in the picture, and give the fractions rooms in the order the path visits them, skipping repeats like \(\tfrac22\). Which room does \(\tfrac23\) get? Which fraction gets room 12? Does every fraction eventually get a room?
Teaser for another night: in 1891 Georg Cantor showed that the decimals between 0 and 1 cannot all be given rooms. There are different sizes of infinity.
Answers
- Room 7 goes to room 8; room 1,000,000 goes to room 1,000,001. Nobody is homeless because every room \(n\) has a room \(n + 1\) to move into.
- Room 7 goes to room 14. Passenger \(k\) takes room \(2k - 1\), so room 15 goes to passenger 8.
- Pair \(n\) with \(5n\). Then 1,000 is paired with 5,000 (and the multiple 1,000 is paired with 200).
- \(x = 0.4999\ldots\), \(10x = 4.999\ldots\), subtract: \(9x = 4.5\), so \(x = 0.5\). For \(y = 0.2727\ldots\): \(100y = 27.2727\ldots\), subtract: \(99y = 27\), so \(y = \tfrac{27}{99} = \tfrac{3}{11}\).
- After four pieces: \(\tfrac12 + \tfrac14 + \tfrac18 + \tfrac1{16} = \tfrac{15}{16}\), leaving \(\tfrac1{16}\). After \(n\) pieces the leftover is \(\tfrac1{2^n}\), which halves every step. Halving a positive number never gives zero, but you can make it smaller than any amount you name, which is exactly what "the sum is 1" means.
- Move everyone from room \(n\) to room \(3n\). Now rooms of the form \(3k - 2\) (1, 4, 7, …) and \(3k - 1\) (2, 5, 8, …) are all empty. Bus A's passenger \(k\) takes room \(3k - 2\); bus B's passenger \(k\) takes room \(3k - 1\). Any finite number of buses works the same way.
Stretch. The path order, skipping repeats, is \(\tfrac11, \tfrac12, \tfrac21, \tfrac31, \tfrac13, \tfrac14, \tfrac23, \tfrac32, \tfrac41, \ldots\) (\(\tfrac22\) is skipped as a repeat of \(\tfrac11\)). So \(\tfrac23\) gets room 7. The next diagonal is \(\tfrac51, \tfrac42, \tfrac33, \tfrac24, \tfrac15\), of which only \(\tfrac51\) and \(\tfrac15\) are new: rooms 10 and 11. Room 12 goes to \(\tfrac16\), the first fraction of the next diagonal. Every fraction sits on some diagonal, every diagonal is finite, and the path reaches every diagonal, so every fraction gets a room. The fractions are the same size of infinity as the whole numbers, which surprised everyone, Cantor included.