h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I saw an Open University program a while back on this topic and it proposed this situation.

What if a customer leaves?

Rather than leave an empty room, get everybody to shift down one room. The hotel will still be full.

But you don't have to!
Infinite number of rooms = N (N being all natural numbers)
If somebody leaves, the full rooms are N \ {x} (x being the room number of the one who left)
This number is still infinite, but the hotel isn't full anymore.
On the other hand, you are right:
If you get everybody to shift rooms, the hotel _will_ be full.

It depends on how you define "full". If full means "no empty rooms", it's not full without the shifting. If, however, full means "having as many guests as there is room for in all the rooms", then it's full even if one room is empty. Lovely little paradox there, eh? =)