1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – man_in_green_shirt Jul 26 '15 at 14:22
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Jul 26 '15 at 14:30
  • $\begingroup$ @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... $\endgroup$ – N. S. Jul 26 '15 at 14:58
  • $\begingroup$ 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$. $\endgroup$ – man_in_green_shirt Jul 26 '15 at 15:04
  • $\begingroup$ 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 $\endgroup$ – man_in_green_shirt Jul 26 '15 at 15:05
0
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – man_in_green_shirt Jul 26 '15 at 14:32
  • 1
    $\begingroup$ @man_in_green_shirt $((c+n)^2+c+n)/2$ is the $c+n$ triangular number, not the $c+n-1$... $\endgroup$ – N. S. Jul 26 '15 at 14:51
  • $\begingroup$ That's also true, I was just going off what was on wikipedia en.wikipedia.org/wiki/… $\endgroup$ – man_in_green_shirt Jul 26 '15 at 14:59
  • $\begingroup$ I'll edit the article now $\endgroup$ – man_in_green_shirt Jul 26 '15 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.