“HILBERT’S GRAND HOTEL: We now describe a paradox that shows that something impossible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each occupied by a guest. When a new guest arrives at a hotel with a finite number of rooms, and all rooms are occupied, this guest cannot be accommodated without evicting a current guest. However, we can always accommodate a new guest at the Grand Hotel, even when all rooms are already occupied.” Discrete Mathematics and its Applications by Rosen.
First, let’s move all the current guests to odd-numbered rooms.
We move the guest in room number n, for n>1, to room 2n+1. In this way, we can accommodate all current guests in odd-numbered rooms (1,3,5,7,…) leaving all even-numbered rooms empty for the new guests.
In the case of the new guests, we assign room number 2n to the guest n. In this way, all the new guests will be accommodated in even-numbered rooms.
Therefore, we accommodate a countable infinite number of guests arriving at Hilbert’s fully occupied hotel without evicting any current guests.
Related exercises:
- 3. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set
- 4. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
- 6. Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel closes all the even numbered rooms for maintenance. Show that all guests can remain in the hotel
- 7. Suppose that Hilbert’s Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel
- ∗9. Suppose that a countably infinite number of buses, each containing a countably infinite number of guests, arrive at Hilbert’s fully occupied Grand Hotel. Show that all the arriving guests can be accommodated without evicting any current guest