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:



Scalia’s Liberal Streak

The conservative justice’s most brilliant—and surprisingly progressive—moments on the bench.

Colorado Is Ground Zero for the Fight Over Female Voters

There’s a Way to Keep Ex-Cons Out of Prison That Pays for Itself. Why Don’t More States Use It?

The NFL Explains How It Sees “the Role of the Female”

The Music Industry Is Ignoring Some of the Best Black Women Singing R&B


Theo’s Joint and Vanessa’s Whiskey

No sitcom did the “Very Special Episode” as well as The Cosby Show.


The Other Huxtable Effect

Thirty years ago, The Cosby Show gave us one of TV’s great feminists.

Cliff Huxtable Explains the World: Five Lessons From TV’s Greatest Dad

Why Television Needs a New Cosby Show Right Now

  News & Politics
Sept. 18 2014 8:20 PM A Clever Attempt at Explaining Away a Vote Against the Farm Bill
Sept. 18 2014 6:02 PM A Chinese Company Just Announced the Biggest IPO in U.S. History
The Slate Quiz
Sept. 18 2014 11:44 PM Play the Slate News Quiz With Jeopardy! superchampion Ken Jennings.
  Double X
Sept. 18 2014 8:07 PM Crying Rape False rape accusations exist, and they are a serious problem.
  Slate Plus
Behind the Scenes
Sept. 18 2014 1:23 PM “It’s Not Every Day That You Can Beat the World Champion” An exclusive interview with chess grandmaster Fabiano Caruana.
Brow Beat
Sept. 18 2014 4:33 PM The Top 5 Dadsplaining Moments From The Cosby Show
Future Tense
Sept. 18 2014 6:48 PM By 2100 the World's Population Could Be 11 Billion
  Health & Science
Sept. 18 2014 3:35 PM Do People Still Die of Rabies? And how do you know if an animal is rabid?
Sports Nut
Sept. 18 2014 11:42 AM Grandmaster Clash One of the most amazing feats in chess history just happened, and no one noticed.