Ropes and Dwarfs in a Munich Subway

People in Germany like Math! After my recent trip to Bonn, Germany, I visited my friend Maria in Munich, Germany for a weekend. She was wonderful and showed me all around town. One thing about her that has always impressed me was how into mathematics she is. When I met her in Toronto last year, I distinctly remember thinking that her interest in mathematics (she is a PhD student in Classics) came from her German education. My trip to Munich only reinforced this.

My Bavarian friend Maria.

The Rope Problem

It started with a math problem… We were waiting in the subway station Friday night and it was going to be a whole ten minutes (!) until the subway was to arrive, so to fill the time I told Maria one of my favourite math puzzles:

(The Rope Problem) You have two pieces of rope and a lighter. Each piece of rope takes exactly 1 hour to burn. Find a way to measure exactly 45 minutes.

You should think about this question, but I’ll talk about it below; there’s a story I’m in the middle of telling! Maria liked the problem and begun talking her way through it. I asked her some leading questions and it was clear she was getting close. The train came and we hopped on. Within a minute she solved it and quickly blurted it out with me nodding enthusiastically and encouragingly. (You know that feeling of finally cracking a good problem!) Then a young woman who was sitting next to us on the train turned to Maria and said “Can you repeat your solution? I was thinking about your problem on the platform, but couldn’t solve it.” Maria goes on to explain, pointing out the relevant details and the woman nods with understanding. “That’s a pretty good problem!” she ends with and we go on our way.

I was pretty impressed with the people of Munich! My good impression wouldn’t end there though…

The Australian Pub

Maria took me to an Australian pub to meet three of her friends who are studying law.

Bruce, Bruce, Bruce, Bruce…

After chatting for a bit (and getting some beers) Maria told them the Rope problem and one of the guys immediately said “No hints!” and went into the tank to think about it. After about 20 minutes of the rest of us chatting he came up with the answer.

We then proceeded to swap math puzzles! Over beers on a Friday night! With non-mathematicians! I was overjoyed, and it just played into my thoughts that Germans love math.

The Dwarf Problem

Here’s one of the problems that I was told that I had never heard before.

(The Dwarf Problem) A clan of dwarfs live in a dark cave. They each have a red hat or a green hat, but the cave is so dark that no one can see any of the hats. One day a horrible monster says he will destroy their home unless they can sort themselves out into the red-hatted dwarfs and the green-hatted dwarfs. Each dwarf walks out of the cave one at a time and decides where it will stand. Outside of the cave they cannot communicate, but they can see everyone else’s hats. Find a way so that all of the red-hatted dwarfs are on one side and all of the green-hatted dwarfs are on the other.

This problem is pretty fun, so you should think about it!

The Rope Problem – Revisited

Back to the rope problem. First, here’s something that doesn’t work: I fold the rope into half, and then in half again and only burn three quarters of the rope. This doesn’t work because you don’t know that the rope is “evenly distributed”, that is, it might take 55 minutes to burn through the first half of the rope (which is very dense), and then 5 minutes for the last half (which is not very dense).

Ok, now try again.

One useful tactic (which is used a lot in mathematics) is to identify the strategies which cannot possibly work and stop thinking about them.

“How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?” -Sherlock Holmes (Sir Arthur Conan Doyle)

For example, you now know that folding the rope in half doesn’t work, so stop trying to make it work. It is very natural to want to fold the rope in this problem, but that doesn’t help you, so stop letting it steal your time.

This picture is not helpful.

Now instead, think about the things you can do. The problem involves burning the ropes, so what actually happens? We light one end of a rope and it takes an hour to burn. Can we modify this in any way? Adapt it? Repeat it?

Well what happens if we burn the rope at both ends…

The Dwarf Problem – Revisited

In the dwarf problem the first thing to realize is that the first dwarf cannot possibly do anything wrong. It doesn’t matter where the dwarf stands. Now for the second dwarf we have to do just a bit of thinking: what doesn’t work? Well Dwarf 2 can’t just stand far away from Dwarf 1 because if they have the same colour then they are screwed. So now we can stop thinking about this, we know that Dwarf 2 has to stand next to Dwarf 1.

I googled “Dwarfs in a line”

Now what does Dwarf 3 do? We know that he has to stand next to the current dwarfs (1 and 2), but here’s where we have to do some thinking. If he sees dwarf 1 and 2 have the same colour, he just stands next to Dwarf 2, if they have different colours then where should he stand? If you figure this out you will have solved the problem.

The Rope Problem – The Ends

Did you figure out what happens if you burn one rope at both ends? Well, I’ll tell you: the rope burns twice as fast, so it burns down in exactly 30 minutes. That looks useful!

Pedagogically this picture should not have a rope in it.

Now what about that second rope? We can measure exactly 30 minutes, but now where do we get 45 minutes from…

The Dwarf Problem – Solution

A dwarf who walks out will see one of the following scenarios:

DwarfSo where should the new Dwarf go? Well, they should go in between the green dwarf and the red dwarf at the transition point.

If all the dwarfs do this they will end up with all the greens on one side and all the reds on the other!

The Rope Problem – The End – End – WAIT! – End

Have you figured out how to involve that other rope yet? Well we can only do things like burn ends of rope. So to start we can only do one of four things:

  • Burn no ends. (This is stupid, don’t do this.)
  • Burn one end of one rope. (This will measure exactly one hour.)
  • Burn both ends of one rope. (This will measure 30 minutes.)
  • Burn one end of each rope. (This will measure one hour.)
  • Burn both ends of both ropes. (This will measure 30 minutes.)

There is only one option missing so far. What is it?

Watch this while you think. (I haven’t figured out how to embed videos yet.)

Burn both ends of one rope, and only one end of the other. After 30 minutes you will have a rope with exactly 30 minutes of “burning time left” and one of its ends burning. At that point you start burning the other end and it will finish burning in 15 minutes. Kablam! 45 minutes measured!