Hilbert's paradox of the Grand Hotel

Reminds me of the proof showing that the set of all fractions are countably infinite.

If there were one person for every natural number, then you could put every even-numbered person in room n/2 (where n is the number for that person) and still fill up the entire hotel.

This is because even numbers are infinite, and you can find a one-to-one relation with natural numbers (just divide the even number by 2).

In that case, the infinite hotel is filled, and you still have an infinite amount of people outside it that you can accommodate (the odd-numbered ones) :)

What is the math concept that allows for a hotel with infinitely many rooms in the first place?

One way of (somewhat) formalizing this is to say that you have a set containing infinitely many rooms, and another set containing infinitely many tenants. Intuitively, it does not seem unreasonable that you can give every room its own tenant. Once you do this, then the hotel is "full" in the sense it is impossible to find an empty room.

Of course, we can also think about giving each tenant her own room, which also seems possible. If we can do both of these things, we say that the set of rooms is the same size (or cardinality) as the set of tenants. It is worth noting, that not all infinite sets are the same size [0]. For the purpose of Hilbert's paradox, I believe it is far to assume that we are dealing with countably infinite sets [1]. The mathematical result in Hilbert's paradox is that if you add elements to a countably infinite set, the result is still countable infitite.

[0] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

[1] That is to say, sets which are as large as the set of natural numbers.

I've posed exactly these problems to children about 15 times now. Most children 10 and up I've talked to can figure out the first (one more guest) easily enough, the second (an infinite bus of new guests) with a little help, and the third (infinitely many infinite buses) if I draw a picture.

It helps a lot to be precise and use concrete examples. "Hilbert has an infinite hotel. We have to be careful with infinities, though, so I'll tell you what that means. If you think of a number zero or bigger, any number at all, Hilbert's hotel has a room with that number on it. Think of a number. ('2 million!') Yep, he's got that room. ('Six googolpillion!') Yep, he's got that room."

"A guest comes into the hotel and asks, 'Mr. Hilbert, do you have one more room?' Mr. Hilbert says, 'Sure!' He picks up his magic phone that calls everyone in the hotel at the same time and gives all the guests exactly the same message. After they do what he says, there's one room empty. What does he tell them to do?"

When they invariably come up with "Move up one room," it helps to belabor a couple of points. First, reformulate it as, "Look at your room number, add 1, and go to that room." (This helps them figure out "Multiply your room number by 2" as the answer to the second problem.) Second, dwell on who goes where, and whether it's a problem. "Where does the guest in room 0 go? ('Room 1.') Doesn't that have someone in it? ('Yes. Oh, no it doesn't, because he went to room 2!')"

No child has figured out my favorite fourth problem, but then it took mathematics until Cantor to figure it out, too.

"An uncountable group of people shows up at the hotel. Let me tell you what that means. They all have infinite name tags, all filled with As and Bs. Every possible name tag is in the group. [Give example names. Blow raspberries to do it.] The head of the group, whose name is 'AAAAAAAAAAAAAA...' [said with a blank look, trailing off] asks Mr. Hilbert if he has room in his hotel. Mr. Hilbert says 'No!' Why does he say that?"

Let them stew for a bit, and ask questions. Going on: "Mr. Hilbert says, 'OK, tell you what. If you give me a room assignment, I can always find someone you left out.' How does Mr. Hilbert do that?"

You can illustrate this with a game, using only four-letter names. Write down something like

AAAA BBAA BABA AABA

"Can you find a four-letter name that's missing?" Play this a few times, and then ask, "Can you come up with an easier way that doesn't make you think of all the names in turn?" Show them how to flip the letters along the diagonal, and then extend to infinite names.

I've had 2 kids and 1 adult follow this to the end. It's always mind-blowing for them, though, no matter how far they get. I follow up with this:

"That stuff they taught you in school, that stuff a lot of people say they hate, is arithmetic. This is math."

EDIT: Come to think of it, I actually helped a friend's 11-year-old daughter decide that she didn't hate math using these problems. She's probably still bummed about being stuck doing arithmetic for now, though...

If you're interested in this subject, can I suggest Everything and More by David Foster Wallace? (Yes, that DFW.) Sure, as some reviews describe in painful detail, some of it is mathematically sketchy. On the other hand, it's a pretty good discussion of issues around infinity, such as Zeno's (and everybody else's and their cat's) paradoxes (paradices? paradise?), and why a theory of the infinite is so darn necessary.