DO the math, DON'T overpay. We make high quality, low-cost math resources a reality.

Monday, November 23, 2015

The Grand Hotel

One of my favorite mathematics stories/folktales/thought experiments/jokes is that of David Hilbert's Grand Hotel, where Hilbert is of course the renowned mathematician you may know of already. Despite its appearance as just a rather strange mathematical folktale, it's based around true, yet counterintuitive mathematical properties of infinite sets. Though the story has many different versions by many authors, you can read my rendition of it below.

Here's how the story goes, in its most comprehensive form:

David Hilbert, mathematician, has opened up in Boston a Grand Hotel with infinitely many rooms: each room has one of the natural numbers on its door. In the opening ceremony, he proudly proclaims the Grand Hotel will always have room, no matter how many people want to stay.

At nine o'clock on opening night, the Boston Red Sox arrive, seeking some luxury after their big win that day. As you may know, there are infinitely many players in the Boston Red Sox, each of whom has one of the natural numbers on his jersey. Upon seeing them, Hilbert smiles, and directs each player to the room whose number is the number on his jersey. As the players fill up the rooms, he does not, however, illuminate the 'NO' on his 'VACANCY' sign.

At ten o'clock, the manager of the Red Sox arrives at the Grand Hotel, having left just behind the team bus but somehow getting caught in traffic the team narrowly escaped. He asks Hilbert for a room, and Hilbert, despite all the rooms being full, doesn't bat an eyelash. Hilbert leans into the intercom, and tells the Red Sox, "Will everyone please move to the room with number one greater than that of his current room?"

So, the Sox start moving, with the player with jersey number 1 finding the next room up vacant, since the one with number 2 has left, player number 400 finding room 401 available, player 7335 finding room 7336 open, and so forth. All the Sox have their rooms, and yet the manager is now free to occupy room number 1. Hilbert, of course, still leaves the 'NO' dark.

At eleven o'clock, the despondent Yankees finally show up, in need of a place to stay after their harrowing defeat. After finding that the Grand Hotel is full, they nearly leave, but Hilbert tells them, "Hold on." He leans over toward the intercom once more, and addresses the hotel. "Will everyone kindly move to the room whose number is twice that of his current room?"

Once again, the Red Sox begin moving, each finding the room he's moving to empty, since the previous occupant is heading further up the building. At the end, all the Sox and their manager are comfortably sitting in the even-numbered rooms, while the odd-numbered rooms are open for the taking. There's infinitely many of those, and Hilbert calmly sends each Yankee to the room twice his jersey number, plus 1—room number 1 is left open for the Yankees' manager, who never shows up, having of course left the city in disgust.

In the morning, the Sox and Yankees depart, without too much conflict between them. At seven in the evening the following day, on recommendation from those baseball teams, the entire NFL arrives in the Grand Hotel's lobby. There are infinitely many teams in the NFL, one for each natural number, each with infinitely many players with natural numbers on their jerseys. By now, Hilbert has wised on to the notion that there'll probably be more infinite collections of people showing up later this evening, so he wants to leave some room this time. Thinking for a moment, he directs the football players to break out their calculators, and then for each to head to the room with number 2a3b, where a is that player's team's number, and b that player's jersey number on that team.

As the football players all head off to their rooms, which are distinct by the uniqueness of prime factorization of natural numbers, Hilbert kicks back with a smile. When the similarly doubly infinite whole NBA arrives, the mathematician sends them to rooms 2a3b5, and even as the organizations for the infinitely many different kinds of sports nameable in the English language arrive one by one, all of them get cleanly housed  in rooms 2a3b5c, where c is the number of that sport, without even breaking into numbers divisible by 7.

On the next day, Hilbert is feeling pretty confident that his hotel can fit any collection of guests, no matter how infinite. Of course, as he thinks this, into the lobby walks a humble tour group from England—infinite in size. However, these tourists have no jersey numbers to go by. Instead, each has the infinite decimal expansion of one of the real numbers between 0 and 1 on his or her nametag, and among them, all those real numbers appear once each. Thinking for quite a while, Hilbert devises an ingenious mathematical scheme for boarding these guests he thinks will work, and proceeds to fill up the hotel. However, as he's sitting in his office, a knock sounds from the door.

Standing there is a young man from the tour group, looking fairly cross. Hilbert asks him what seems to be the problem. "Well," comes the reply, "I haven't got a room!"

Hilbert's face twists with indignation, and he replies, "What? I thought I gave everyone a room!"

"You certainly didn't, and I can prove it!" The guest walks over to the infinite chalkboard on which  Hilbert's written down all the guests' room assignments, and scrawls his own number above it with a piece of chalk.

Then, he starts going diagonally down the list of tourist numbers, circling the nth decimal place in the number of the guest in the nth room. 

"Now look here!" he begins. "The guest in the first room, the first decimal place of her tour group number is 1, but mine is 2! The guest in the second room, the first decimal place of his number is 5, but mine is 6! In fact, each decimal place of my number is one greater than that in the number of the guest in the corresponding room, and therefore I can't be any of the guests who has a room! And if you put me somewhere, there will be some real number that then has the same property as mine does now, and so you'll never be able to fit us all in! There simply cannot be a one-to-one correspondence between the real numbers between zero and one and the natural numbers, Hilbert. Some infinities are larger than other infinities." 

Hilbert's countenance withers under the tourist's explanation, and he shuts down the Grand Hotel in shame the next day.