# Triangular number method - Hilbert's hotel

There is a hotel with and infinite number of numbered rooms, each occupied by a single guest. An train with an infinite number of (numbered) coaches, each with an infinite number of (numbered) seats, each occupied by a person, arrives at the hotel. Can you find space for all these people? One method, suggested on Wikipedia, is the triangular number method:

Those already in the hotel will be moved to room $(n^2+n)/2$, or the nth triangular number. Those in a coach will be in room $((c+n)^2+c+n)/2$, or the $(c+n-1)$ triangular number, plus $(c+n)$. In this way all the rooms will be filled by one, and only one, guest.

So the person who's in room $1$, stays in room $1$. The person in room $2$, moves to room $3$. The person in room $3$ moves to room $6$, and so on.

What about the new guests? If they are moved to room $((c+n)^2+c+n)/2$, can't that still be a triangular number and hence already occupied?

You missed the "plus $(c+n)$". That makes the guest's room number different from the triangular numbers and from all other guests. Moving the second guest to room $3$ makes one space, which is filled by the first person in the first car. Moving the third existing guest to room $6$ opens two spaces, filled by the second person in the first car and the first person in the second car.

• Doesn't the first person in coach one ($c=n=1$) go to room $3$ as well? The $(c+n-1)$th ($1$st) triangular number is $1$, and if you add $c+n=2$ you get $3$ – man_in_green_shirt Jul 26 '15 at 14:22
• I saw that as I was typing it up. There needs to be a slight update in the formula. The addition should just be $n$, as shown in this article – Ross Millikan Jul 26 '15 at 14:30
• @man_in_green_shirt If you plug $c=n=1$ in the formula you don't get 3. The labeling of the triangular numbers in the problem is either non-standard or wrong... – N. S. Jul 26 '15 at 14:58
• I was plugging it into the "the $(c+n-1)$ triangular number part. However, as you pointed out, the formula should have $c+n-1$ instead of $c+n$. – man_in_green_shirt Jul 26 '15 at 15:04
• This way, using the standard labeling of the triangular numbers (the first one is $1$, the second one $3$, the third one $6$) the solution works – man_in_green_shirt Jul 26 '15 at 15:05

Those in a coach will be in room $((c+n)^2+c+n)/2$, or the (c+n−1) triangular number, plus $(c+n)$.

$((c+n)^2+c+n)/2+c+n$ is not a triangular number.

P.S. Just to clarify, $((c+n)^2+c+n)/2$, is the $c+n$ triangular number, and no $((c+n)^2+c+n)/2+c+n$ cannot be a triangular number as $$((c+n)^2+c+n)/2 < ((c+n)^2+c+n)/2+c+n < ((c+n+1)^2+c+n+1)/2$$

Indeed the first inequality is obvious, while the second is equivalent to: $$c^2+2cn+n^2+c+n+2c+2n <c^2+n^2+1+2c+2n+2cn+c+n+1$$ which after canceling reduces to $$0<2$$

• Sorry, I meant "can't that still be a triangular number"? For example, take $c=n=1$. The $(c+n-1)$th ($1$st) triangular number is $1$, and if you add $c+n=2$ you get $3$, which is a triangular number – man_in_green_shirt Jul 26 '15 at 14:32
• @man_in_green_shirt $((c+n)^2+c+n)/2$ is the $c+n$ triangular number, not the $c+n-1$... – N. S. Jul 26 '15 at 14:51
• That's also true, I was just going off what was on wikipedia en.wikipedia.org/wiki/… – man_in_green_shirt Jul 26 '15 at 14:59
• I'll edit the article now – man_in_green_shirt Jul 26 '15 at 14:59