The Uncountable Hotel

This story is a follow-up to The Infinite Hotel.

David Hilbert had been getting quite some attention with his Infinite Hotel. Georg Cantor, a fellow mathematician who was always in for an impossible challenge, wondered if he could design an even bigger hotel. So that when it was completely full, there would be no way all those guests could ever fit in Hilbert's hotel. No matter what clever trick Hilbert would come up with (and as we know, he had quite a few of those).

So Cantor started to think. Hilbert's hotel had an infinite amount of rooms, each denoted by its own room number. The first was number 1, the next number 2, and so on — all the way to infinity. Basically, there was a room for every possible positive (whole) number. How could he design more rooms than that? Hmmm... what if, maybe, his hotel was to include rooms for all negative numbers as well? A list of all rooms would then go on indefinitely in both the positive and the negative direction! Surely he would then have twice as many rooms as Hilbert did.

Cantor soon realized it was not going to be that easy. Infinity times two? That's still infinity. Just arrange the rooms so that you can match them, and you'll see:

Cantor's Room Number	1	-1	2	-2	3	-3	4	-4	...	∞
Hilbert's Room Number	1	2	3	4	5	6	7	8	...	∞

The idea sounded good at first, but the above shows that Hilbert's hotel would still be able to house every potential guest in Cantor's hotel. It doesn't matter if you change the labels on the doors; the number of rooms is still infinite.

The Ant On An Elastic Rope

An ant starts to walk along an elastic rope which is 1 km long, at a speed of 1 cm per second (relative to the rope it is crawling on). While this happens the rope is uniformly stretched by 1 km per second (i.e. after 1 second it is 2 km long, after 2 seconds it is 3 km long, etc.). Assume the rope will never break and we have an infinite amount of time on our hands. Will the ant ever reach the end of the rope?

Here's a hint: Yes, yes it will.

The Cube Dovetailing Puzzle

A cube consists of two halves, interlocked together as pictured above. The cube looks like that on all of its four sides. How would you separate the two halves without cutting, breaking or distorting them in any way? The answer is inside...

The Missing Euro

“Three guests check into a hotel room. The clerk says the bill is €30, so each guest pays €10. Later the clerk realizes the bill should only be €25. To rectify this, he gives the bellhop €5 to return to the guests. On the way to the room, the bellhop realizes that he cannot divide the money equally. As the guests didn't know the total of the revised bill, the bellhop decides to just give each guest €1 and keep €2 for himself.

Now that each of the guests has been given €1 back, each has paid €9, bringing the total paid to €27. The bellhop has €2. If the guests originally handed over €30, what happened to the remaining €1?”   ^source

The Mixing Problem

Say you have two barrels, one containing wine and the other containing an equal amount of water. You take a cup of wine from the wine barrel and add it to the water. If you want, you can stir it some — or not, it doesn't matter. Then take a cup of that wine/water mixture and return it into the wine barrel. The cup should hold the exact same amount so that both barrels once again contain equal volumes (but now mixed). The question is: which one of the mixtures is purer?

Thought about it? The answer is that both mixtures are equally pure! (← click to spoil)

The Supertask

In Greek mythology, Achilles was a hero of the Trojan War. Some 2500 years ago, philosopher Zeno of Elea included him into one of his paradoxes. Achilles was quite the runner... or maybe the paradox shows otherwise.

Suppose Achilles was in a 100 meter foot race with a tortoise. The tortoise is given a 25 meter head start. It would seem obvious that when Achilles eventually starts running, he will easily overtake the tortoise and then comfortably reach the finish line (with time to spare). Looking at it logically though, one could wonder how Achilles can ever beat the tortoise.

The Survey

A census taker rings the doorbell and a woman opens. She informs the census taker that she lives in the house with her three sons. “What are the ages of your boys, please?” the census taker asks.
“When you multiply all their ages, the result is 72,” the woman cryptically informs him.

The census taker has a confused look on his face, so the woman adds: “The sum of their ages is the same as the housenumber of the house next door.”
He finds this rather odd, but walks to the house next door, only to return shortly after. “I still don't know, can you give me another hint?”

“Sure,” the woman says, “my oldest son likes strawberries.”
The census taker nods and writes down the ages. What are they?

The Infinite Hotel

This story is a follow-up to The Highest Number.

David Hilbert had worked hard for it, but after what seemed like an eternity, his Grand Hotel was finally completed. So many people had been involved in building it, it was impossible to keep count. But there it was, up and running, with more guests coming in every day. And Hilbert's Grand Hotel was grand alright. You see, this hypothetical hotel had an infinite amount of rooms. A feature Hilbert was keen to advertise: “The hotel that always has a room available!”

Business was good. Hilbert enjoyed his tasks as manager, as quirky situations tend to occur a lot in a hotel with infinitely many rooms. Such a situation often required a mind-bending solution, just the kind of challenge Hilbert liked. And with the hotel quickly filling up, things were about to get crazy.

The Coin Flip

Here's a quick riddle. Setup: you are blindfolded, wearing thick gloves. There are twenty coins on the table in front of you: ten are heads and ten are tails. You do not know which; you cannot see them because of the blindfold and you cannot feel them because of the gloves. The only thing you can do is flip coins upside down or move them around.

You are to divide the coins into two equal groups (thus ten coins each). The assignment is to get the same number of heads and the same number of tails in both groups. How can you do it? No peeking!

Hint: The solution is easy. But reasoning to that point... less so!

The 20 Prisoners And The Hats

The warden from The 100 Prisoners And The Light Bulb is up to another one of his sick games! He puts 20 death sentenced prisoners together in a cell and explains the rules of their upcoming ordeal.

“Tomorrow, at the execution, I will give you a chance to go free. I will queue you up randomly and put a hat on your head. The hat is either red or blue. You cannot see the color of your own hat, only those of the prisoners in front of you. You will not be allowed to look behind you, nor are you allowed to touch, or talk to the other prisoners in any way. To be clear, the last prisoner will only see the 19 prisoners in front of him. The second-to-last prisoner will only see the 18 prisoners in front of him, and so on.”

The warden grins. “Starting with the last person in the row, I will ask a simple question: What is the color of your hat?”

“If he answers correctly, I will set him free. But you can guess what happens when the answer is wrong. He will be put to death immediately. Regardless of the outcome, I will then move to the prisoner in front of him, and ask the same question. From the last one in the row to the first one, you will all be asked.”

The warden lowers his voice. “And another thing. I will tolerate no cheating. If anyone answers anything besides ‘red’ or ‘blue’, I will execute you all right then and there!”

As he leaves, the warden sarcastically shouts: “Good luck tomorrow!”

The twenty prisoners can still talk freely during the night, so they are having heated discussions about how to free as many prisoners as possible. This turns out to be a difficult task. What is the most prisoners that can definitely be saved, and how?

The Exponential Folding

How many times do you need to fold a piece of paper (A4 size) in half, to make it reach the moon? Assume that the paper is 0.1 mm thick and that the distance to the moon is 384,403 kilometers (238,857 miles) — the accepted average.

When you calculate this, you should find that there are only 42 folds necessary. Welcome to the world of exponentials!

The Counterfeit Coin

You are given 12 golden coins, though you know that one of them is a counterfeit. The counterfeit coin can be detected because it does not weigh completely the same the others. But at the moment you don't know which coin it is, nor do you know whether it will be lighter or heavier.

Unfortunately, all you have is a scale of the classical type. It is the kind where there are two balanced dishes. By putting objects in, the scale will indicate that one side is heavier than the other (the dish will hang lower) or that each side weighs the same.

How can you find the counterfeit coin by only weighing three times? And is the coin lighter or heavier than the others?

The Road To Safety

A lone traveler comes upon a fork in the road. One path leads to safety, the other will lead to certain doom. At the fork there are two twin brothers and each guards one of the paths. One always lies and the other always tells the truth — you do not know who is which.

You can only ask one yes/no question to one of the brothers. What should your question be to find the safe path?

This is one form of a well known logical puzzle known as ‘Knights and Knaves’. This particular format was used in the 1986 film Labyrinth.

The puzzle has many variations and in the future I will post one that is annoyingly more complex. For now, let's see what the answer should be for this one.

The Rickety Bridge

Andrew, Beth, Carol and Daniel are on vacation and have spent the day exploring the mountain ranges in Yellowstone National Park. Having lost track of time, darkness is setting in and they are in a hurry to get back. But then there is a rickety old wooden bridge on their path, suspended high over a deep ravine. There's a warning-sign stating that the bridge will only be able to carry the weight of two persons at a time.

No-one is willing to cross the dangerous bridge without the light of a flashlight... unfortunately the group only has one of those with them. They can't risk throwing it, thus it needs to be carried back and forth.

Because of their different ages and fitness levels they will all cross at different speeds. Andrew can cross in 1 minute, Beth in 2 minutes, Carol in 4 minutes and Daniel in 5 minutes. For each duo, the slowest will of course determine the duration of crossing.

Soon it will be night and pitch black. Therefore the group wants to cross the bridge in the minimum time possible. Andrew thinks for a moment and then announces it can be done in 12 minutes. No trick. How?

The Highest Number

What is the highest number there is? Let's try and find out by working our way up. To save myself from having to write down a lot of digits, let me first explain the scientific notation:

• 1 × 10² = 1 × 10 × 10 = 100
• 1 × 10³ = 1 × 10 × 10 × 10 = 1000
• 1 × 10⁴ = 1 × 10 × 10 × 10 × 10 = 10000

Basically, powers of 10 can be used to define the number of zeros that follow the ‘1’. So here's some large numbers you might know: a million, a billion, a trillion, a quadrillion... These can be written respectively as 10⁶, 10⁹, 10¹² and 10¹⁵. You might knew these first few, but that list actually goes on for a while. Take for example a vigintillion, which is 10⁶³. Are there any higher?

Of course! How about the googol? It is notated as 10¹⁰⁰. That's a ‘1’ with a hundred zeros! Is this the largest number? Nah, we can put at least the centillion (10³⁰³), septuagintacentillion (10⁵¹³) and the millinillion (10³⁰⁰³) on the table.

We need to do better than this, so let's push it into crazy territory. A googolplex is 10^googol — yes, that's 10 to the power of a googol. A ‘1’ with a googol zeros. 10¹⁰¹⁰⁰. Fine! It is a 1 with 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 zeros. So as you can see I just wrote out a googol. I cannot write out a googolplex: there is not enough room in our universe to do so. See, the number of atoms in the observable universe is estimated to be around 10⁸⁰. This means that writing down a googolplex requires far more zeros than there are atoms in the universe!

The Pigeonhole Principle

The Pigeonhole Principle states: If 10 pigeons are put into 9 pigeonholes, then at least one pigeonhole must contain 2 pigeons.

...Okay, I suppose it is not a very difficult principle. So let's use it in scenarios that are a bit harder to grasp right off the bat.

Your drawer contains 10 red socks and 10 black socks. You just woke up, barely got your eyes open, just reaching inside the drawer without looking. What is the fewest number of socks you need to take out to be sure to end up with a matching pair?
The answer is: three socks (← click to see). In this example there are 2 pigeonholes/sock colors (red and black) so with 3 pigeons/socks one of those must always contain a pair. Still with me?

Taking it up a notch then. Your drawer contains 2 red, 8 black, 10 blue and 16 white socks. Once again, what is the fewest number of socks you need to take out to be sure to end up with a matching pair?
Five socks. Think of the pigeons!

I guess that still makes sense. How about this: There must be at least two people living in Rome with the exact same number of hairs on their head. Even if the bald don't count. And that's not a probability either, that's a fact. How do we get to make such a claim?

The Bottle Imp

The ‘Bottle Imp Paradox’ is similar to the Unexpected Hanging, but it's a fun one.

“You are offered the opportunity to buy, for whatever price you wish, a bottle containing a genie who will fulfill your every desire. The only catch is that the bottle must thereafter be resold for a price smaller than what you paid for it, or you will be condemned to live out the rest of your days in excruciating torment.

Obviously, no one would buy the bottle for 1¢ since he would have to give the bottle away, but no one would accept the bottle knowing he would be unable to get rid of it. No one would buy the bottle for 2¢ either: he would be unable to sell it since we just established that no one would take it for 1¢. Similarly, no one would buy it for 3¢, and so on. However, for some reasonably large amount, it will always be possible to find a next buyer, so the bottle will be bought.”   ^source

The 100 Prisoners And The Light Bulb

One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate with each other. Each day, the warden will choose one of the prisoners at random, and place him in a central interrogation room for an hour. A prisoner can be chosen any number of times; thus it could happen a prisoner is chosen multiple times while another is yet to be picked. The interrogation room contains nothing but a light bulb and a light switch. The prisoner can see whether the light is on or off, and – if he wishes – can toggle the light switch. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time.

If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. So obviously the announcement should only be made if the prisoner is 100% certain that it is true!

The warden leaves, and the prisoners huddle together to discuss their fate. This is the last time they can speak with each other! Can they devise a system that will guarantee their freedom?  

The Monty Hall Problem

Suppose you're on a game show, and you are given the choice of three doors: behind one door is a car; behind the other two are goats. Naturally your goal is to win the car, which is equally likely to be behind each door.

You pick a door (e.g. #1), and the host (who knows what's behind each door) opens another (e.g. #3) which has a goat. This means there are two doors left, one with a car and one with a goat. You are now given the opportunity to switch your choice (from #1 to #2). Is it to your advantage to do so?

Since you can't know which of the two remaining doors has the car, and since your initial pick had a chance of one-third, you might think that it does not matter. The chance is still ¹/₃ and you might as well stay with your original choice, right? Wrong! Switching actually doubles your chances to ²/₃.

The Triangle Dissection Fallacy

Take a look at the above picture, and agree with me that this is weird. We see two triangles, and based on the grid they are both the same size. A quick count of the grid boxes tells us that the surface of both triangles should be 13 × 5 ÷ 2. All the pieces are equal in size, yet by shuffling them around we suddenly have a spare grid box!

This does not make any sense. The act of rearranging the triangle pieces should not change the surface area. What's going on here?