Infinity Hotel Paradox

Date: 09/15/1999 at 12:29:23
From: Mr. Tuesday Evening
Subject: Infinity Paradox

Our math class has a paradox we can't figure out. Can you make heads 
or tails of it?

A hotel has an infinite number of rooms. Each room has already been 
assigned to a person with the corresponding room number on his or her 
shirt; i.e. the person with a shirt that says 438 is in room 438, etc. 
Now an infinite number of buses come, each containing an infinite 
number of people. They all want a room. Explain how all of these can 
be accommodated while still maintaining the original premise that each 
person gets his or her own room. Also, you can only use positive 
integers, no negatives or irrational numbers.

Thanks,
-MTE

Date: 09/15/1999 at 13:45:05
From: Doctor Rob
Subject: Re: Infinity Pardox

Thanks for writing to Ask Dr. Math.

One way to do this is as follows.

Let the original occupants of the hotel be considered "Bus Zero."

Denote the people by an ordered pair, (B,N), where B is the bus number 
and N is the number of the person on that bus.

Arrange the pairs in a rectangular grid:

      :       :       :       :
    (0,4)   (1,4)   (2,4)   (3,4)   ...
    (0,3)   (1,3)   (2,3)   (3,3)   ...
    (0,2)   (1,2)   (2,2)   (3,2)   ...
    (0,1)   (1,1)   (2,1)   (3,1)   ...

Now take the person in the diagonal containing (0,1) only, and give 
him the first room.

Then take the people in the diagonal from (0,2) to (1,1), in order, 
and give them the next two rooms.

Then take the people in the diagonal from (0,3) to (2,1), in order, 
and give them the next three rooms.

Then take the people in the diagonal from (0,4) to (3,1), in order, 
and give them the next four rooms.

Then take the people in the diagonal from (0,5) to (4,1), in order, 
and give them the next five rooms.

Continue in this way forever.

Now every person in every bus will have a room. Person N in bus B will 
have been taken in the diagonal from (0,B+N) to (B+N-1,1). In fact, he 
or she will have been given the following room number R:

     R = (B+N)*(B+N+1)/2 - N + 1.

No two people will have the same room. (I leave that to you to 
verify.) Room R will be on the D-th diagonal, where

     D = (1+sqrt[8*R])/2, rounded down to the nearest integer,

and it will be assigned to the N-th person on Bus B, where

     B = R - D*(D-1)/2 - 1,
     N = D*(D+1)/2 - R + 1.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/