Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This evening I had a discussion with a friend of my about a mathematical riddle and the concept of 'infinite'

The riddle

Imagine a hotel with an infinite amount of rooms, and all of the rooms are occupied. At that moment a bus arrives with an infinite amount of people who all want a room in that hotel. Possible or not, and how?

Possible answer (according to friend)

The owner of the hotel lets everyone who is currently sitting in a room, move to a room further. In that way the first chamber will be available.

To be honest I am not really knowledgable at math, but something tells me that this is equivalent to shifting the problem. Thanks to this 'solution' there is always somebody without a room, or not? After all, if someone moves to the room further one will never find an empty room. The person after him also has to move and the person after him also etc. etc.

I think there can never be more people in that hotel as all (infinite) rooms were already filled with an infinite number of people. (infinite + 1 is impossible, right?)

Is it because of my limited understanding of the term 'infinity' and am I missing something, or is something wrong with the riddle?

*Sorry for the English, I hope it's clear. *

share|improve this question
3  
This is known as Hilbert's Grand hotel. –  Asaf Karagila Sep 29 '12 at 23:49

4 Answers 4

up vote 5 down vote accepted

After all, if someone moves to the room further one will never find an empty room.

The first room is clearly empty: there's nobody moving into it.

The only way a person could fail to move into the next room is if they were in the last room. But then there would only be finitely many rooms, so clearly this particular hotel doesn't suffer from this problem.

The main point of this example is to vividly demonstrate one of the ways in which infinite collections differ from finite ones.

(infinite + 1 is impossible, right?)

In this case, we're adding ordinal numbers. And you can add them. The ordinal number describing the hotel rooms is called $\omega$. It is essentially just the sequence of natural numbers.

When you add two ordinal numbers, you essentially just place one after the other. So if we draw a picture of 1:

*

and a picture of $\omega$

            • ....

then to get $1 + \omega$, we place 1 first, then $\omega$ next:

            • ....

Looks the same, doesn't it? That's what happens in the hotel. And that's because $1 + \omega = \omega$.

Incidentally, if we add the other way, $\omega + 1$, we get an ordinal number that's bigger than $\omega$. One way to draw it is

            • .... | *

The pipe (|) is a decoration to indicate that the .... really refers to an infinite sequence of asterisks (*), and they all are located to the left of the pipe. This is so it's not confused with something like

      • ... *

in which the ... would usually be interpreted as a finite number of asterisks that we were too lazy to write out.

One particularly important thing to note about $\omega + 1$ is that last asterisk doesn't have an immediate predecessor. That's another unusual feature that infinite ordinal numbers (except for $\omega$ have: they can have elements that have infinitely many things before it, but none of them are immediately before it.

share|improve this answer
    
Great! This really makes sense. :-) –  Sebass van Boxel Sep 30 '12 at 12:19

You might be interested in reading this

share|improve this answer

Thanks to this 'solution' there is always somebody without a room, or not?

Who?

The person in the 1st room now has room 2. The person in the 1284th room now has room 1285. In fact, there's nobody in the hotel that doesn't have a room: it is true, in some sense, that "infinity + 1 = infinity" (and I think Hurkyl explained this very well via ordinals).

If that doesn't convince you, think about it this way: what if you (our hypothetical hotel owner) built a new room (called 0) to accommodate a new guest, but then - a few days later - decided that a room called 0 was silly, and so simply renumbered all the rooms, renumbering 0 as 1, 1 as 2, and so on. What has changed? Nothing - the (numerical) structure of your hotel is the same, everyone has a room, and your new guest has been accommodated.

So that's a nice easy way to get one extra guest in, as long as you're prepared to mildly inconvenience infinitely many people to do so. And if we can get one extra guest in, we can get as many as we like in: if a bus carrying 50 people turns up, just get everyone to move to (their own room + 50), or equivalently, add an extra 50 rooms to the front. No problem there.

But if a bus carrying infinitely many people turns up, you can't shift everyone to (their own room + $\infty$) - as you will quickly realise, when the non-mathematician in room 17 that complains he couldn't work out which room to move to (even when he used his calculator!). Adding infinity to a number doesn't make sense. All of the rooms in your hotel have been given nice, solid, honest, finite room numbers - the "(17+$\infty$)th" room (whatever that means) doesn't exist. (There are infinitely many finite numbers, but you shouldn't confuse this with 'infinite numbers' (whatever such things might mean).)

So what can you do? Remember, there is a stipulation that you can't insert rooms at the end (because there is no end - right?), but we've already seen that you can insert rooms at the beginning (because there is a beginning, namely room 1). In fact, we can insert rooms anywhere that we like, provided that place is easy to point to: e.g. you can tell everyone in rooms 6, 7, 8, ... to move to rooms 7, 8, 9, ... and leave a gap in room 6. (Equivalently: insert a room $5\frac{1}{2}$ between rooms 5 and 6, and then renumber the rooms.) Now, we obviously can't just plonk infinitely many rooms at the start, because that has the problem I mentioned before - everyone has to end up in a nice (finite) room.

[A question you might ask at this point is: why can't you just add rooms 0, -1, -2, -3, ... and stick your busful of guests in those? Well, you can, practically, of course. But then it becomes rather harder to renumber the rooms, so that they are numbered 1, 2, 3, ... again. Remember that we're not actually allowed to invent new rooms - I introduced this idea as a tool to show you that moving infinitely many people across finitely many rooms wasn't going to change your hotel structurally, or leave anyone without a room, or anything like that. You can't do anything that changes the numerical structure of your hotel.]

So you might decide to insert an unoccupied room between every two occupied rooms. That is, you might decide that you want rooms 1, 3, 5, 7, 9, ... to be free, and rooms 2, 4, 6, 8, 10, ... to be occupied. Ah, that's easy: tell everyone to move to the room number that's double their own. Now the man in room 17 is happy again.

What if two infinite buses turn up? Well, you could just do the same thing again, twice. That would annoy a lot of your guests, but you probably wouldn't care, not least because you'd be making a lot of money out of this. Likewise three or four infinite buses. But what if infinitely many buses turn up, all at the same time? You can't ask your guests to move to double their own room number infinitely many times - the man in room 17 is unhappy again, because he doesn't know which room he will end up in after infinitely many moves ("what is $17\times 2^\infty$??", he complains). You're trying to shunt him infinitely far away, and he doesn't like this.

But there's no need to panic. Calmly announce that you want all your guests to move to double their own room number (once only!), and watch them stare in amazement:

Let me label the buses a, b, c, d, ... (let's pretend there are infinitely many letters!), and let me label their passengers a1, a2, a3, ..., b1, b2, b3, ..., and so on. Now simply admit them to your empty rooms (1, 3, 5, 7, ...) in the following order:

a1,

b1, a2,

c1, b2, a3,

d1, c2, b3, a4,

...

Do you see the pattern? Do you see why everyone (even if they're the millionth passenger on the billionth bus) is going to have a finite room number?

share|improve this answer

If the rooms are numbered 1, 2, 3, 4, . . . and all are occupied, and everyone shifts one room further up, then only one room becomes vacant. But if everyone moves to the room that bears twice the number of the room he's in already, then infinitely many rooms become vacant. The latter way works if the number of new customers is what is called "countably infinite".

"Countably infinite" means they are numbered 1, 2, 3, 4, . . . . , so that for each member of this numbered collection of customers, you will reach that customer after counting through only finitely many terms of this sequence.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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