Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 8.6.5 Proof by Case Enumeration

A common way to exploit the divide and conquer idea to prove a general claim is to divide the universe into a set of distinct cases. Of course, we must make sure that every element of the universe is included in one of the cases. But, if we can do that, we can then reason separately about each different case. Once we’ve done that successfully, we have a proof that the claim is in fact universally true.

There’s a whole class of puzzles called Knights and Knaves. In all of them, there’s an island on which live two kinds of people, knights, who always tell the truth, and knaves, who always lie. We’ve already (back in the chapter on Boolean Logic Proofs) considered one example of this sort of puzzle. We called it Fork in the Road. Let’s now consider another one.

Suppose that Peachy, an islander, makes the statement, “At least one of my friend Figgy and me is a knave.” What are Peachy and Figgy?

We can divide our analysis into two cases:

• Peachy, the speaker is a knight. In that case, he must be telling the truth. Then there has to be a knave and it’s not Peachy. So it must be Figgy. So we have that Peachy is a knight and Figgy is a knave.

• Peachy, the speaker is a knave. In that case, he must be lying. But then both he and Figgy would have to be knights, which can’t be true since we already know that Peachy is a knave.

Thus the only choice is our first one: Peachy is a knight and Figgy is a knave.

Nifty Aside

If we’re working with simple Boolean expressions, it doesn’t matter whether everyone lies or everyone tells the truth, as long as we know which it is. If I know that you’re lying, I just put a not in front of whatever you say in order to get the truth. Of course, if claims carry more information, it could be really annoying for me to have to ask enough questions to get the answer I want. For example, if I know that you will lie and I want to know how much your car cost, I don’t want to have to get the (known to be false) answer, “25,000”, and then ask again and get another (known to be false) answer, “25,001”, and so forth, until I can eventually figure out what price you don’t mention.

But the idea that one can know for sure that people are telling the truth is interesting. If you haven’t seen it, you might want to watch the movie, The Invention of Lying.

Consider a tic-tac-toe grid with the squares labeled as in (A):

1 2 3 1 2 3 4 5 6 O X 6 7 8 9 7 8 9 (A) (B)

Suppose that X moves first to square 5 and that O moves next to square 4. Then we have a board as shown in (B).

Prove that X can choose a move such there is nothing O can do to prevent X from winning.

The proof is by case enumeration:

If X moves to 1, then there are five choices for O: 2, 3, 6, 7, 8, and 9. Consider them:

• If O moves to 2, 3, 6, 7, or 8, then X moves to 9 and wins.

• If O moves to 9, X moves to 2. Then O has the options of 3, 6, 7, or 8. Consider them:

  • If O moves to 3, 6, or 7, then X moves to 8 and wins.

  • If O moves to 8, then X moves to 3 and wins.

Nifty Aside

Of course, tic-tac-toe is a trivial game. It’s easy to play by enumerating all the cases. But what about interesting games like chess? It turns out that, while people can’t play winning chess by enumerating all the possible move sequences, computers can win by enumerating “enough” possible move sequences. For example, in 1997 IBM’s Deep Blue beat the then reigning human chess champion Garry Kasparov. While Deep Blue has some other chess knowledge, its main approach was to look ahead enough moves to be able to decide what to do next.