### A Riddle in the Dark

Four friends are trying to cross a dark tunnel with a single torch.

Aragorn can cross the tunnel in 1 minute.

Legolas can cross the tunnel in 2 minutes.

Gimli can cross the tunnel in 4 minutes.

Frodo can cross the tunnel in 5 minutes.

The tunnel is very narrow, so they can walk alone or in pairs, but no more than two at the same time.

If two friends are walking together, they walk at the speed of the slower one.

They must use the torch while walking through the dark tunnel.

The torch will be extinguished in 12 minutes.

Can they make it? How?

~~~

p.s. I've found a marvelous proof of the Goldbach Conjecture which this p.s. is too short to contain.

Aragorn can cross the tunnel in 1 minute.

Legolas can cross the tunnel in 2 minutes.

Gimli can cross the tunnel in 4 minutes.

Frodo can cross the tunnel in 5 minutes.

The tunnel is very narrow, so they can walk alone or in pairs, but no more than two at the same time.

If two friends are walking together, they walk at the speed of the slower one.

They must use the torch while walking through the dark tunnel.

The torch will be extinguished in 12 minutes.

Can they make it? How?

~~~

p.s. I've found a marvelous proof of the Goldbach Conjecture which this p.s. is too short to contain.

## 17 comments:

I like your blog. Keep up the good work.

NanoGeekTech

Aragon carries Gimli, (or Frodo).

Legolas carries Frodo, (or Gimli).

Love your blog, and the Science Fiction Fantasy forum on BlogCatalog. :D

That's cheating :)

The slowest of them holds the torch, the rest line up behind with one hand on the man in front of them, and they all parade down the hall single-file in 5 minutes.

How you doing, Uri? :)

That's cheating too :)

If they "use the torch" unlit, is that cheating? :D

Aragorn + Legolas =2

Aragorn back = 3

Gimli and Frodo = 8

Legolas back = 10

Aragorn + Legolas = 12

(came from BlogCatalog)An interesting blog you got here. I guess pasha solved it?

When I first came across the dancing silhoutte a few months ago I spent an hour staring at it...

Well done Pasha!

The more complicated question is:

What is the general solution ('algorithm') for these kind of problems?

I think the solution must rely on these two principles:

1. the two fastest are the 'runners'.

2. Always move a slow guy with another slow guy.

I can think of an easy reduction to LP problem with integers, which is NP-complete. So you can expect that an algorithm for the general solution will be inefficient. But that is the beauty of the riddle, otherwise why bother?

How about this recursive solution:

- Sort elements by crossing time (k1, k2, ..., kn)

1. k1, k2 cross.

2. k1 goes back.

3. kn, k(n-1) cross.

4. k2 goes back.

5. solve the problem for k1, k2, ... k(n-2).

Aragorn and Legolas (2 minutes),

Aragorn returns (1 minute),

Frodo and Gimli (5 minutes),

Legolas returns (2 minutes),

Aragorn and Legolas (2 minutes).

Total time: 12 minutes. :)

@Ross,

Well done! You are correct!

Uri,

I think there is a solution that can bring them in 10 minutes,

but it involves a time machine....

Anyway, great blog.

Ran

@Mainzer,

I knew it was a mistake letting you know about this blog... Just kidding :) Welcome to Urikalization!

Ghosty didn't cheat. He just outsmarted the problem with superior logic.

In the military, he'd be the guy you want in charge.

Post a Comment