The Hotel With No Vacancies
The puzzle
A hotel has rooms numbered 1, 2, 3, … with no last room, and every single one is occupied. A new guest arrives and asks for a room.
Can the manager accommodate them without anybody leaving? And what if a coach arrives carrying infinitely many guests?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
The manager cannot find an empty room - there are none. But he can ask people to move.
Hint 2
For the coach, moving everybody along by one is not enough. Move them somewhere that leaves infinitely many gaps.
Show the answer Hide the answer
Yes to both. Ask the guest in room n to move to room n+1, which frees room 1. For the coachload, ask the guest in room n to move to room 2n, which frees every odd-numbered room - and there are infinitely many of those.
How to get there
Every guest has a room to move into, because every n has an n+1. Nobody is left without a room, and room 1 is now empty. No room was empty before and none was created; the guests were simply re-indexed.
For infinitely many new guests, moving along by one frees only one room. Moving the guest in room n to room 2n puts every existing guest in an even room and leaves rooms 1, 3, 5, 7, … free. The coach passengers take those.
Nothing here is a trick of wording. It is what "the same size" means for infinite sets: two sets are the same size when their members can be paired off, and n to n+1 and n to 2n are both perfect pairings. The whole numbers and the even numbers really are the same size, which is the part that offends intuition built on finite things.
The technique worth keeping
For infinite sets, size means "can be paired off one to one", not "has fewer members". Any question about fitting more things into an infinite collection is answered by producing the pairing explicitly.