Imagine a hotel. Now imagine that this hotel is unlike any other:
This hotel can accommodate a countably infinite number of patrons. Wait, did I just say countably infinite? What the hell does countably infinite mean? Isn't infinity just infinity?
No! One of the topics that they really harped on during my four years as a math major at UVA is the fact that not all infinities are created equal. For example, the infinity that we're most familiar with, that of the positive integers (1,2,3,4,...), is smaller than the infinity of real numbers between 0 and 1.
Why? Think about this: if I asked you to find an integer between 1 and 2, you can't. As a matter of fact, you wouldn't be able to find an integer between any two consecutive integers. In math terms, this means that the positive integers aren't dense.
But the real numbers between 0 and 1 are different. If I were to tell you to find a number between 1/3 and 1/2, you could say 2/5. If I asked for a number between 1/100 and 2/100, you could say 3/200. Even if I asked for a number between .33333 and .333333, you could say .333332. Unlike the positive integers, there is a number between any two arbitrary real numbers in the interval from 0 to 1, making the real numbers between 0 and 1 dense, meaning the infinity between 0 and 1 is bigger than that of positive integers.
Holy shit that was a ton of really boring math jargon.
Now back to the hotel paradox. Let's say that one night, the hotel manager really has his work cut out for him: a countably infinite number of buses, each containing a countably infinite number of passengers show up. And they all want rooms.
How can our hotel manager accommodate each of his guests with their own unique room? Hmmmmm.
Here's a little hint: if there were two buses filled with a countably infinite number of guests, he could tell everyone in bus one to go to an even numbered room and all of those in bus two to go to an odd numbered room (because the even integers and odd integers are both countably infinite, remember?).
Any ideas? I'll wait. Cue Jeopardy music.
Times up! Here's the solution, one that you would most likely only know if you spent four years barely passing all of your math classes.
In case you didn't know, there is an infinite number of prime numbers (that would have been a helpful tidbit of knowledge). Therefore, the hotel manager could assign each of the countably infinite buses a unique prime number. Then, he could assign each passenger on each bus a power of said prime number.
So the third passenger on the second bus would be in room 3^2 (aka 9), the fifth passenger on the fourth bus would be in 7^5 (aka 16,807), and so on and so forth.
Since each number will only have two factors (one and the prime it's a power of), now two passengers will ever be assigned to the same room. And since the powers of prime numbers are all positive integers, there will definitely be a room for everyone.
And there you have it! Feel free to stump your friends with this little brainteaser at your next get-together.
Isn't math fun? Yes?
NERD!
