Proof by Contradiction: a Fairy Tale

Once upon a time there was an evil king. He had all he could desire: a huge castle, servants, riches, and more power than he could shake a stick at. But as time wore on, even these could not comfort him, nor could they solve his one problem (and this wasn’t his usual problem, which was that he was so powerful even he had to obey himself.) No, this problem ran much deeper. Even with everything he had, there was one thing he couldn’t have: friends. He would try to become friends with people — but he could never have a true friend, because eventually friends disagree, and he was an evil king, and you don’t disagree with evil kings. So he became lonely. And lonelier. And as he became lonelier and lonelier, he became bitterer and bitterer and bittererer.

Finally, he became so enraged at everyone who had friends, that he began to devise an evil plan. He would hold an enormous feast, and after the feast, all the guests would be lined up. “And then,” he said aloud, in his evil planning voice, “I will begin to draw numbers from a hat, and with each number drawn, one guest shall die! Moreover, as I have no friends, each guest will die when the number of friends they have at the feast is called!” His plan completed, the King began to put it in motion. Until he hit a fatal snag.

He spent weeks and weeks trying to devise a guest list, but as you’ll recall, he was so powerful he had to obey his own commands, and he had said that with each number called, one guest would die. But try as he might, he could not figure out a guest list (even with his evil party planner) that would invite guests where each guest had a unique number of friends at the feast. Finally, the king sent for his evil royal mathematician, the evilest mathematician there was. “O King,” said the mathematician, “how my I serve your Royal Evilness.”

“Help me with my guest-list, and I shall reward you beyond your wildest imagination,” the king responded, detailing his dastardly plan.

Cowering in sudden fear, the mathematician spoke, her voice trembling. “Your Majesty, it — it is not possible.”

“Explain yourself,” the king roared.

“Well, Your Evilness,” she spoke again, “suppose you invite k guests. Since you aren’t counting guests being friends with themselves, for each guest there are k-1 other guests to be friends with. So the most friends any guest can have is k-1. The least number of friends any guest can have, clearly, is 0. Which means that for any guest there are k possible numbers of friends: 0, 1, 2 ,3, …, or k-1. But now, you see, you have k guests and k numbers-of-friends you need to pair. If you want each guest to have a unique number of friends, you must therefore pair some guest with each of the k numbers-of-friends. Thus one guest, Xanthia, will have 0 friends, and also another guest, Bartholomew, will have k-1 friends. But since Bartholomew has k-1 friends and there are k people counting him, he must be friends with Xanthia. But then Xanthia and he are friends, which makes no sense, since Xanthia has no friends and thus Bartholomew and Xanthia aren’t friends. This is clearly impossible, and so each guest cannot have a unique number of friends, and so therefore there must always, no matter who you invite, be two guests with the same number of friends.”

And with that, the king suddenly ceased to exist. For, you see, his existence had become the battleground of two great Necessities: the Necessity of his power said the feast must exist, and the Necessity of the Laws of Mathematics said the feast must not exist. Thus, his existence was a contradiction, and therefore, he did not exist.

And so, children, the kingdom was saved from the evilest, powerfulest, loneliest King in the world.