David Hilbert invented this paradox to help us understand infinity. Imagine a grand hotel with an infinite number of rooms.
Imagine the hotel is completely full. In an ordinary hotel, that would mean there is no room for another guest. But in this hotel, even though there is an infinite number of guests, we can still make room. Assuming the rooms are numbered, we can simply ask the guest in Room 1 to move to Room 2, the guest in Room 2 to move to Room 3, and so on. Each guest must move from Room n to Room n + 1. This is possible because the number of rooms is infinite. The new guest can then move into Room 1.
This process can be repeated for any finite number of new guests. If 50 new guests show up, then each existing guest will move from Room n to Room n + 50. The Infinite Hotel and other fascinating philosophical concepts are discussed in Logicomix.
What if a bus carrying an infinite number of new guests show up? They too can be accommodated. Each existing guest must move from Room n to Room 2n. So the guest in Room 1 moves to Room 2, the guest in Room 2 moves to Room 4, the guest in Room 3 moves to Room 6, and so on. The existing guests will therefore be occupying only the infinitely many even-numbered rooms. The infinite number of new guests can then move into the infinitely many odd-numbered rooms.
What if an infinite number of buses, each carrying an infinite number of passengers, arrives at the Grand Hotel? As long as we are dealing with the countable infinity of the natural numbers, we can find a way. One method, explained by Jeff Dekofsky in the TED video below, relies on the fact that there is an infinite quantity of prime numbers. For the existing guests, we use the first prime number, 2, and assign each guest to the room number equal to 2 raised to the power of their current room number. The guests on the first bus are assigned to the room number of the next prime number, 3, raised to the power of their seat number on the bus. For the next busload, the same procedure is followed, using the next prime number, 5. Each resulting room number only has 1 and the natural number powers of its prime number base as factors, so there are no overlaps (although there are empty rooms).
This is an example of a veridical paradox: it leads to a counter-intuitive result that is provably true.