Infinity Hotel has an infinite number of rooms, all of which are currently occupied.

1) A new guest arrives, describe how he would be allocated a room.
2) An infinite number of new guests arrive, describe how they would all be allocated rooms
3) An infinite number of Infinite Coaches arrives (each carrying an infinite number of guests), describe how these guests would all be allocated rooms.

None of them would be allocated a room, they are all occupied.

The answer to all of these is the same: They wait until checkout to get their rooms.

Ha, I missed the "all of which are currently occupied" on my first read, was this supposed to be tricky like that? (My eyes were drawn to the pretty numbered list.)

If it has an infinite number of rooms all of which are occupied, then the only way for there to be anyone left to arrive is for the infinite rooms to be occupied by finite people.

1. Move each guest in room n to room n + 1, then the first room will be free for the new guest.
2. Move each guest in room n to room 2n, freeing up an infinite number of rooms.
3. First, empty the odd number rooms the same way as problem 2. Then, for coach number i, put coach's passengers in room p[sup]n[/sup] where p is the (i + 1)th prime number.

How about a solution that doesn't involve knowing all the primes?

Hire an Asian kid that does know all the primes!

Or, assume that each coach has a license plate number, pretend the hotel is coach 0. Also assume the seats of the coaches are numbered. To find out which room a guest should go to, interleave the digits of the coach number with the seat (or room) number. So the guest in room 162 goes to room 106,020, and passenger on seat 58 of coach 521 goes to room 502,518. Notice that the number with fewer digits is padded, so you're effectively interleaving 058 with 521.

[Edit: By the way, this one taken from Wikipedia]

Seems pretty simple. The hotel is full. Explain to me how I'm wrong, though, if I am.

Infinity (rooms) - Infinity (occupants) = 0.

The other explanations here seem to assume that infinity can grow beyond the size of infinity, when in fact they are equal.

Look up the diagonals solution, it's the most straightforward explanation I've seen.

Oh, I kind of remember that. Talked about it in class years ago... it definitely was the most straightforward.

CM, if you have infinitely many rooms, what is to stop you from continually moving to the next room?

My other solution is to offer a free ride to the satellite hotel in the same city.

I tried to tell him that in IRC but he insists that infinity is "special".

I mean I can sorta see where he's coming from.

If you add one more person, you have Infinity + 1 people in Infinity rooms so it's 1 too many... but Infinity + 1 (or any positive constant) is still Infinity, so you have just enough rooms. Still if you introduce "degrees of infinity" (IE when you do limits you can sometimes cancel out infinities that conflict in order to simplify the problem) the latter might not be considered valid I guess. Anyways I'm not really sure whether you or Detty is "right" on the issue, and maybe you BOTH are.

Infinity - Infinity does not always = 0. It could be any real number because it's indeterminate. I'm not sure if it can be imaginary, but I don't think it can.

I guess that's what throws me off, is that the concept of one infinity being smaller than another infinity seems to fly in the face of the entire concept of infinity itself. That is, by saying one is smaller than another, you're setting bounds on the infinity, and it is then no longer infinity.

Edit: Let me add that I get that an infinite set between, say, 0 and 1 would be smaller than an infinite set between 0 and 100. I'm going off the constraints of the problem, of integers with no upper limit.

Nothing except the infinitely many occupants who are in those rooms. There's no "end" of the line.

I almost see that question as the 0.999... = 1 issue. Saying that there will eventually be a room an occupant can move into is like saying there is eventually a place where 0.9999... will end, a "final" nine (or a "final" occupant).

The number of characters in the infinite set in between 0 and 1 would be the same as the infinite set between 0 and 100 because they're both infinite.

The problem people have, as I see, is that they treat "infinity" as a number. It really isn't. Talking about doing mathematical operations like "infinity - infinity" is meaningless. What you can do is talk about infinite sets, like the set of all integers. The set of all positive integers is also infinite, even though intuitively you might think it would only be half the size as the set of all integers. Same goes for the set of all even integers, or the set of all multiples of 10, etc. In fact, you can have infinitely sparse infinite sets, which is the key to the third question.

It all gets even more interesting when you consider sets that are not only infinite, but are also "bigger" than other infinite sets. For example, the set of all real numbers between 0 and 1 is a "bigger" infinity than the set of all integers, or even the set of all rational numbers. Turns out, of course, that there's actually an infinite number of "sizes" of infinity. The infinity we're used to talking about is actually the "smallest". All very fascinating, really, but don't think about it too hard because it will melt your brain.

For additional brain-melting reading, I recommend: http://en.wikipedia.org/wiki/Aleph_number

I've read two books recently that discuss the infinity hotel. I recommend Music of the Primes by Marcus du Sautay

There are indeed different sizes of infinity. The set of all integers is infinite. The set of all numbers between 1 and 2 is also infinite. However, this second set is infinitely bigger than the first. See Aleph Numbers (I'm on an iPod touch so I can't link easily, I apologise)

I posted before this acknowledging that, but also to say that I am working in the constraints of the problem, where both sets of infinity are integers starting at presumably 1, or whatever.

No, that's incorrect. [0..1] is a proper subset of [0..100], so [0..100] must be larger. That is to say, every number in [0..1] is also in [0..100], but [0..100] also contains other numbers, thus it is larger.

That logic doesn't work. It's like saying that the primes are a proper subset of the integers, so the primes are of lower cardinality. It's not true.

edit:

You can prove that set A ([0,1]) and set B ([0,100]) have the same cardinality by setting up a bijection between them: for any a in A and b in B, define the function f that maps A onto B, such that f(a) = 100*a. Every element of B corresponds to exactly 1 element in A, and vice versa. So we say the two sets have the same cardinality.

This is true, but think of it this way: when a new guest comes in, put him in room #1. Have everybody else move from their current room (room n) to the next room (room n+1). The new guest is happily settled in his room, and nobody else is ever going to have a problem either. Like you said, there's no end of the line, so everyone else will always have an n+1 to move into.

Larger is kind of a deceptive term. Saying one infinite set is infinitely larger than another infinite set doesn't really have a meaning. "Larger" and "higher order" are not the same thing. Larger is a best a kind of analogy.

Oh, that's true. My mistake.

Answer this then:

Is infinity + 1 > infinity?

I was always under the assumption this isn't true. When you move everyone over + 1, there's still going to be someone there. There is no "last room" to add onto, where someone could move in without there being an occupant already.

the real question is, if the dear lord baby jesus showed up at the infinity hotel, would he have to stay in the infinity manger?

You're right, it's not true. Assuming the infinity you're talking about is the infinite sum of all the integers. <_<

/really doesn't have a handle on this, despite reading a book about it.

I agree with Emon. That's what all professors do anyways

It breaks down because you're thinking of infinity as a number. You can't think of it as a number, not even as an unfathomably large number, it is a concept that behaves very differently to numbers (and the point of the Infinity Hotel problem is to illustrate this).

No, it's quite accurate, the size of a set is defined by the number of elements in it, and you compare sets by producing a correspondence between elements in the two sets. You wouldn't call it a 'higher order', that means something entirely different. You could use the term cardinality, but that's equivalent to size.

ok, can more than 1 guest be in a single room? if so problem solved real easy.

if not then it does not seem like there would be a way to allocate even a single new person a room. yes there would be an infinite number of rooms, but as is already stated all of the infinite rooms are currently occupied so there will never be an unoccupied room so long as there can only be one person per room(again if that is the case).

The problem has already been resolved earlier in the thread. Move everyone in the hotel up one room (there's an infinite number of rooms, so this is no problem) and you have one room free. When every room is occupied, you assume there is no more room in the hotel. Not so with the Infinity Hotel.

But you were just telling CM that infinity isn't a number, because it doesn't behave like numbers do.

I think Obi is right, at least as far as he's found a good colloquial way of expressing the problem. If you think of infinite sets as having "sizes" and trying to compare those sizes, you'll be misled. If you give up on thinking about the size of a set, and try other methods, things start to work better.*

(Not aimed at Mort, but to the thread in general): Think of two sets of things, like the set of seats at your dinner table, and the set of people coming to dinner. If you can come up with a one-to-one correspondence between the members of those sets, then you'd conclude that the two sets have the same size. (If you have a person without a chair, that means there isn't a perfect correspondence, and if you have a chair without a person, again there isn't a 1-1 correspondence.)

It turns out that it's useful to deal with infinite sets in this way, too. Think about the set of all the positive even integers {2,4,6,8,...} and the set of ALL the positive integers {1,2,3,4,5...}. Without thinking about the SIZE of the sets, you'll admit that we can find a one-to-one correspondence between the elements of the two. For every element in set B, multiply it by 2 to find its partner in set A. 1*2=2, so 1 is paired with 2; 2*2=4, so 2 is paired with 4, and so on. Every member of each set is paired with exactly one unique member of the other set. That's why mathematicians would say these two sets have the same "cardinality," because they satisfy a criterion that makes sense for finite sets. (If every guest was matched with exactly one unique chair, and every chair had exactly one guest to sit in it, there would be an equal number of guests and chairs.)




*I say that "things start to work better," but maybe I should say this. There are two ways of talking about the elements in a set. We could count them directly, and talk about the "number of elements in the set". Or we could come up with pairings between the sets, like I described above. For finite sets, those two ways of looking at it coincide. The weird thing about infinity is that the two DON'T coincide for infinite sets. The latter way of working with sets turns out to be way more useful, so mathematicians consider that the "right" way of determining the cardinality of a set.

The problem with thinking about the size of an infinite sense in the usual way, by counting its elements or by thinking about its subsets, is that it's hard to apply to infinite sets:

• You can't count the number of elements, because you'll be counting forever.
• You can't cop out by saying "the number of elements is infinity," either, because infinity isn't a number. Infinity is a linguistic short-hand for "you'll never stop counting" just like "I owe you zero dollars" is a linguistic short hand for "I don't owe you any money."
• Therefore it's just not possible to define the "size of the set" in terms of the number of elements it contains, in the way we'd usually do.

"infinity + 1 > infinity" is an expression that doesn't make sense, because infinity isn't a number that you can perform ordinary operations with.

Like I said in my post above, the trouble is in trying to think about the number of rooms you have vs. the number of guests you have.

Instead, tell me this: under my proposed solution, is there ever a guest who doesn't get a room? Not guest #999, because he can move into room #1000. Not guest #999999, because he can move into room #1000000, and so on. No guest will ever have a problem here, because there's no "last guest" or "last room".


(I shouldn't do this, but to answer your question on your terms--remember that a mathematician would say they don't make sense--: you are right that "infinity + 1 > infinity" is false. In fact, to the extent that it makes sense, infinity + 1 = infinity. But that also shows us that the hotel won't have a problem. It had infinity rooms, so it could accommodate infinity guests. Then it got one more guest, so it had infinity + 1 guests, which is really just infinity guests. So the number of guests it has hasn't changed. So it can still fit everyone, including the new guest.

See why talking about it in these terms is eschewed by mathematicians?)

What's wrong with "higher order"? It may not be the technical term for it, but it communicates the meaning pretty well.

The whole point is that it doesn't have a higher number of elements, because infinity is not a number. It has more numbers, but not in the same way one finite value is larger than another.

But you still haven't explained where all these new guests are coming from when there are already infinite guests - that is, everyone - in the hotel.