Is the Zebra Puzzle really the Hardest Puzzle in the World?

As one random example, consider the famous 100 prisoner problem:

> The director of a prison offers 100 prisoners on death row a last chance. In a room there is a cupboard with 100 drawers. The director puts in each drawer the name of exactly one prisoner in random order and closes the drawers afterwards. The prisoners enter the room one after another. Each prisoner may open and look into 50 drawers in any order and the drawers are closed again afterwards. If during this search every prisoner finds his name in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his name, all prisoners have to die. Before the first prisoner enters the room, the prisoners may discuss their strategy, afterwards no communication of any means is possible. What is the best strategy for the prisoners?

This is not a trick question ("the first prisoner stays in the room for a number of seconds that encodes the names"). There really is no communication, zero. The conditions are exactly as described. The chances of survival aren't 100% but they are way better than the apparently inevitable 2 −100  2^{-100}.

The zebra puzzle will be eventually be solved by anyone with enough time on their hands using any methodical approach, though some people will be faster than others. The prisoner puzzle can stump a really smart person for years, possibly forever. That's the difference between routine work and creativity, between following a recipe and having a flash of inspiration.

Answer by Alon Amit:

No, this puzzle is about as far from being the hardest puzzle in the world as an ant is from being the biggest animal.

Even if we take "puzzle" to mean "a well-defined, honest riddle with a known solution that doesn't require an advanced degree", even under those limiting conditions there are puzzles much harder than this.

The reason is simple: you can easily write a computer program to solve this puzzle, which means that you can solve it yourself with a pen, paper and patience.

Really clever puzzles require ingenuity and insight, and we are pretty far from being able to teach computers to solve them.

As one random example, consider the famous 100 prisoner problem:

The director of a prison offers 100 prisoners on death row a last chance. In a room there is a cupboard with 100 drawers. The director puts in each drawer the name of exactly one prisoner in random order and closes the drawers afterwards. The prisoners enter the room one after another. Each prisoner may open and look into 50 drawers in any order and the drawers are closed again afterwards. If during this search every prisoner finds his name in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his name, all prisoners have to die. Before the first prisoner enters the room, the prisoners may discuss their strategy, afterwards no communication of any means is possible. What is the best strategy for the prisoners?

This is not a trick question ("the first prisoner stays in the room for a number of seconds that encodes the names"). There really is no communication, zero. The conditions are exactly as described. The chances of survival aren't 100% but they are way better than the apparently inevitable [math]2^{-100}[/math].

The zebra puzzle will be eventually be solved by anyone with enough time on their hands using any methodical approach, though some people will be faster than others. The prisoner puzzle can stump a really smart person for years, possibly forever. That's the difference between routine work and creativity, between following a recipe and having a flash of inspiration.

There are lots of really great puzzles requiring a spark of genius. The zebra puzzle isn't one of them.

Is the Zebra Puzzle really the Hardest Puzzle in the World?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s