Hilbert's hotel: infinitely many buses
Tonight's idea
In Hilbert's hotel the full hotel took in one infinite bus: guests moved to the even rooms and the passengers took the odd ones. Tonight is worse. Buses numbered 1, 2, 3, … pull up, each carrying passengers numbered 1, 2, 3, … Every person needs a different room, and the guests already inside must keep one too.
First idea. Draw a grid, one row per bus and one column per passenger, and walk it diagonally, as the fractions sheet did. Every seat is reached eventually. It works, but finding one person's room means counting along the path.
Second idea. Call the existing guests bus 0. Passenger \(k\) of bus \(b\) goes to room \(2^b(2k-1)\): an odd number, doubled \(b\) times. Bus 0 gets the odd rooms; bus 1 gets 2, 6, 10, …; bus 2 gets 4, 12, 20, … To read a room number backwards, halve it until it is odd. The number of halvings is the bus; the odd number left over tells you the passenger.
Watch one: room 100 and bus 5
Who is in room 100? Halve: 100, 50, 25. Two halvings, then odd, so it is bus 2. The odd number 25 is \(2k - 1\) with \(k = 13\), so passenger 13. Check forwards: \(2^2(2 \times 13 - 1) = 4 \times 25 = 100\).
Where does passenger 2 of bus 5 go? \(2^5 = 32\) and \(2 \times 2 - 1 = 3\), so room \(32 \times 3 = 96\). In binary, 96 is 1100000: the five zeros on the end are the five halvings. You met this odd-number-times-power-of-two idea before, as the odd core in the pigeonhole sheet.
Your turn
- Buses 4 and 5 are also in the queue. Write down the rooms for passengers 1 to 4 of each. Do any of your eight rooms clash with the sixteen in the figure?
- Look at rooms 1 to 16. Which of them are missing from the figure? For each missing room, say who gets it.
- Decode rooms 24, 56, 81, 64 and 1000 into a bus and a passenger. Then find the room of passenger 100 on bus 7, and say whether you would rather have done that by counting along diagonals.
- Explain in your own words why no two people get the same room, and why no room is left empty. (Think about what halving a room number tells you.)
Stretch: garages full of buses
Now infinitely many garages arrive, each holding infinitely many buses, each full of passengers. Can everyone still be housed? Hint: use tonight's rule once to give every bus in every garage its own single number, then use it again.
Answers
- Bus 4 (\(2^4 = 16\)): rooms 16, 48, 80, 112. Bus 5 (\(2^5 = 32\)): rooms 32, 96, 160, 224. No clashes: every room in the figure is an odd number times 1, 2, 4 or 8, and these are odd numbers times 16 or 32.
- In the figure: 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14. Missing: 9, 11, 13, 15 and 16. The odd ones belong to bus 0 (the old guests): passengers 5, 6, 7 and 8. Room 16 halves four times to 1, so it goes to bus 4, passenger 1.
- 24 → 12 → 6 → 3: bus 3, passenger 2. 56 → 28 → 14 → 7: bus 3, passenger 4. 81 is already odd: bus 0, passenger 41. 64 halves six times to 1: bus 6, passenger 1. 1000 → 500 → 250 → 125: bus 3, passenger 63. Bus 7, passenger 100: \(2^7 \times 199 = 25{,}472\), one multiplication; the diagonal path reaches that seat after more than 5,500 others.
- No two people share. If two people had the same room number, halving it would give the same number of halvings and the same odd number, so the same bus and the same passenger: they are the same person. No room is empty. Start with any room number. Halve it until it is odd; that always stops, because the number shrinks each time. You get some number of halvings \(b\) and an odd number \(2k - 1\), so the room belongs to passenger \(k\) of bus \(b\). Every whole number is an odd number times a power of two in exactly one way.
Stretch. Yes. Give bus \(b\) of garage \(g\) the label \(2^{g-1}(2b - 1)\). Tonight's argument shows every label 1, 2, 3, … is used exactly once, so the fleet is now just buses 1, 2, 3, … with the old guests as bus 0. Then passenger \(k\) of the bus labelled \(n\) takes room \(2^n(2k - 1)\). No clashes, no empty rooms, and you could do it a third time.