What Is an Example of a Counterintuitive Mathematical Result?

The best answer to any question.
June 4 2014 10:55 AM

What Is an Example of a Counterintuitive Mathematical Result?

This question originally appeared on Quora.

Answer by Michal Forišek, computer science lecturer at Comenius University:


The Hydra game!

Imagine that you are Hercules, and you were given the task to slay the Hydra. Here is one possible hydra:


Courtesy of Michal Forišek

Our hydra is a rooted tree. The root (black, at the bottom) is the body, and the leaves (blue) are its heads. Just like Hercules, you are going to cut off its heads, one at a time. But, just like with the mythical Hydra, each time you cut off one head, it may grow some more in other places. Here's the rule:

You can cut off a head that is connected directly to the root. In that case, nothing grows back. In all other cases, you grow new heads as follows:

  • Let x be the vertex where the head you just cut off was attached to the Hydra.
  • Go down one edge from x, let y be the new vertex.
  • Grow two new copies of the entire subtree you just came from. (We will call this the growth rule.)

A picture is better than words, so here's what happens when you cut off one head of our Hydra. Below, the head we decided to cut off is now dashed, and we show the vertices x and y:  


Courtesy of Michal Forišek

And now we take the subtree we just came from (vertex x and two leaves) and we add two new copies of that subtree at y:  


Courtesy of Michal Forišek

We just cut off one head and got four new heads in return. Not good. Let's try that one more time, this time cutting off the second head from the bottom.


Courtesy of Michal Forišek

Now we have 19 heads. Looks like this Hydra will be pretty tough to kill. You can kill the head at the bottom to go down to 18, but then any next kill will increase the number of heads again.

At this moment your intuition probably tells you that killing a Hydra is a hard job. Sure, some tiny Hydras can be killed—if you have just a body and a few heads, you cut off the heads, and that's it. But if you try killing any nontrivial Hydra, after the first few cuts, your situation will look like in our example. Don't just take my word for it: Try it yourself.  

Now, it wouldn't be too surprising if I told you that you can always win the Hydra game. Instead, I'll tell you something you certainly don't expect: You cannot ever lose the Hydra game. You will always kill the Hydra in finitely many turns, regardless of how large the Hydra is, and in which order you kill the heads.

And it gets better. Let's make the game harder. See the word two in the growth rule? Let's change it to 47. Even with 47 new copies of a subtree added in each turn, you still cannot lose the game.

Let's now change the growth rule as follows: If this is turn N of the game, grow N new copies of the entire subtree you just came from. That is, the longer you play, the faster the Hydra grows. You still cannot lose the game. Regardless of how you play, the Hydra is still guaranteed to die in finitely many steps.

Here's the most awesome version of the growth rule: Pick any positive integer N. Go ahead, make it as large as you wish. You can even pick a different N each time, and make each choice greater than the previous one. Grow N new copies of the entire subtree you just came from.

Guess what? You still cannot lose. Each possible game still has to be finite. There is no way to make an infinite sequence of valid moves.

* * *

Here's a sketch of the proof: We can assign an ordinal to each possible hydra using a recursive formula: A single node gets the ordinal 0, and α node with children α1 through αk (sorted in decreasing order of assigned ordinals) gets the ordinal ωα1 + ... + ωαk, where αi is the ordinal assigned to the tree rooted at αi. It can now be shown that every valid move decreases the ordinal assigned to the hydra. And as there is no infinite decreasing sequence of ordinals, every possible game must be finite.

If you just got lost and scared, here's a bit of intuition behind what's going on in the proof. We basically say that whenever something goes on K steps away from the root, it's infinitely times worse than anything that is going on K-1 steps away from the root. Now, whenever you kill a head, you very slightly simplified something that is K steps away. And even though you get a lot of new stuff in return, all that stuff is only K-1 steps away, and hence the entire result is still simpler than it was before. (That's as good a description as I can give in one paragraph.)

And to top it all off: You may now ask for a simpler proof. You won't get one. Proving that the hydra game is finite is hard. In particular, in 1982 Kirby and Paris proved the following theorem: "Any proof technique that proves that the hydra game is always finite must be strong enough to prove that Peano arithmetic is consistent."

More questions on Quora:


Justice Ginsburg’s Crucial Dissent in the Texas Voter ID Case

Even When They Go to College, the Poor Sometimes Stay Poor

Here’s Just How Far a Southern Woman May Have to Drive to Get an Abortion

The Most Ingenious Teaching Device Ever Invented

Marvel’s Civil War Is a Far-Right Paranoid Fantasy

It’s also a mess. Can the movies do better?


Sprawl, Decadence, and Environmental Ruin in Nevada

Space: The Next Generation

An All-Female Mission to Mars

As a NASA guinea pig, I verified that women would be cheaper to launch than men.

Watching Netflix in Bed. Hanging Bananas. Is There Anything These Hooks Can’t Solve?

The Procedural Rule That Could Prevent Gay Marriage From Reaching SCOTUS Again

  News & Politics
Oct. 20 2014 3:53 PM Smash and Grab Will competitive Senate contests in Kansas and South Dakota lead to more late-breaking races in future elections?
Continuously Operating
Oct. 20 2014 3:40 PM Keeping It in the Family Why are so many of the world’s oldest companies in Japan?
Oct. 20 2014 3:16 PM The Catholic Church Is Changing, and Celibate Gays Are Leading the Way
  Double X
The XX Factor
Oct. 20 2014 1:10 PM Women Are Still Losing Jobs for Getting Pregnant
  Slate Plus
Tv Club
Oct. 20 2014 7:15 AM The Slate Doctor Who Podcast: Episode 9 A spoiler-filled discussion of "Flatline."
Brow Beat
Oct. 20 2014 5:03 PM Marcel the Shell Is Back and as Endearing as Ever
Future Tense
Oct. 20 2014 4:59 PM Canadian Town Cancels Outdoor Halloween Because Polar Bears
  Health & Science
Medical Examiner
Oct. 20 2014 11:46 AM Is Anybody Watching My Do-Gooding? The difference between being a hero and being an altruist.
Sports Nut
Oct. 20 2014 5:09 PM Keepaway, on Three. Ready—Break! On his record-breaking touchdown pass, Peyton Manning couldn’t even leave the celebration to chance.