Proof by Contradiction in Combinatorial Impossibility

The Logic of Contradiction

The formal name for this method is reductio ad absurdum, Latin for "reduction to absurdity." The process is straightforward and relies on a core principle of logic: a statement cannot be both true and false at the same time.

To prove a statement $P$ by contradiction, we follow these steps:

1. Assume the opposite: Begin by assuming that the statement $P$ is false. That is, assume $\neg P$ (not $P$) is true.
2. Work from the assumption: Use logical deductions, definitions, and other known facts to explore the consequences of your assumption.
3. Find a contradiction: Show that this chain of reasoning leads to a contradiction—a statement that is impossible, such as $1=0$ or a claim that a number is both an integer and not an integer. This is a statement of the form $R\wedge \neg R$.
4. Conclude: Since our assumption $\neg P$ led to an absurdity, the assumption itself must be false. Therefore, its opposite, the original statement $P$, must be true.

To see this method in action with a familiar concept, watch the following video from Dr. Trefor Bazett. It demonstrates how to prove that no integer can be both even and odd, which builds nicely on the divisibility definitions from our last lesson.

Proving Impossibility: The Mutilated Chessboard

Now let's apply this technique to a classic combinatorial puzzle. This type of problem, proving that a certain configuration is impossible, is where proof by contradiction truly shines.

Consider a standard 8x8 chessboard. It has 64 squares. We can easily tile this board with 32 dominoes, where each domino covers exactly two adjacent squares.

Now, let's modify the board. Suppose we remove two squares from opposite corners.

The question is: Is it possible to tile this "mutilated" board with 31 standard dominoes?

Trying to tile it might lead to frustration, as you'll always seem to get stuck. But this doesn't prove it's impossible. To prove it, we need a rigorous argument. This is where contradiction, combined with a clever insight, comes in. The insight is to color the board.

The following resource introduces a powerful concept for impossibility proofs called the Parity Principle and applies it to this very problem.

Let's break down the proof by contradiction you just read:

Statement (P): It is impossible to tile the mutilated chessboard with 31 dominoes.

1. Assume $\neg P$: Assume it is possible to tile the mutilated chessboard with 31 dominoes.
2. Analyze Consequences:
   • A standard chessboard has 32 black and 32 white squares.
   • The two opposite corners have the same color (in our image, both are black). Removing them leaves 30 black squares and 32 white squares.
   • Each domino, no matter where it's placed, must cover exactly one black square and one white square.
   • Therefore, a complete tiling of 31 dominoes must cover exactly 31 black squares and 31 white squares.
3. Find the Contradiction: Our assumption implies that the board must be covered by 31 black and 31 white squares. However, we know the mutilated board has 30 black and 32 white squares. This is a contradiction: the number of black squares must be both 31 and 30.
4. Conclude: Our assumption that a tiling is possible has led to an absurdity. Therefore, the assumption is false, and the original statement is true: It is impossible to tile the mutilated chessboard.

This coloring argument is a cornerstone of combinatorial reasoning. It transforms a complex geometric problem into a simple counting problem.

For a quick and engaging visual walkthrough of this same proof, you can watch this short clip.

Another Parity Argument: The Handshaking Lemma

The idea of parity as an invariant extends far beyond tiling puzzles. Let's look at a foundational result in graph theory.

Problem: At a party, some people shake hands. Prove that the number of people who have shaken an odd number of hands must be an even number.

This might seem abstract, but it's another impossibility proof in disguise. It's proving that "It is impossible for an odd number of people to have shaken an odd number of hands."

Proof by Contradiction:

1. Assume the opposite: Assume that an odd number of people have shaken an odd number of hands.
2. Analyze Consequences:
   • Let's model the party as a graph, where people are vertices and handshakes are edges. The number of hands a person shakes is the degree of their vertex.
   • Every handshake (edge) connects two people (vertices), so it adds 1 to the degree of each of those two vertices.
   • This means that every handshake increases the total sum of all degrees by 2.
   • Therefore, the sum of the degrees of all vertices in any graph must be an even number. (This result is known as the Handshaking Lemma).
3. Find the Contradiction:
   • We have established that the sum of all degrees must be even.
   • Now consider our initial assumption: there is an odd number of people with odd degrees. Let's say the remaining people have even degrees.
   • The sum of any number of even numbers is even.
   • The sum of an odd number of odd numbers is always odd.
   • Therefore, the total sum of degrees would be (sum of odd degrees) + (sum of even degrees) = (odd) + (even) = odd.
   • This is our contradiction: The sum of degrees must be even (from the lemma) and odd (from our assumption).
4. Conclude: The assumption that an odd number of people shook an odd number of hands leads to a contradiction. Thus, the number of people who shake an odd number of hands must be even.

You can also find this proof explained concisely in the Teaching the parity principle article you looked at earlier. It's presented as the "Graph-Theoretic Puzzle."

Key Takeaways

• Proof by contradiction is a powerful technique for proving a statement $P$ by assuming $\neg P$ and showing this leads to a logical absurdity.
• This method is especially effective for impossibility proofs in combinatorics, where you need to show that a certain arrangement, configuration, or outcome cannot exist.
• A common strategy in combinatorial contradiction proofs is to find an invariant—a property, like parity, that is preserved by the rules of the system. If the starting state and the desired goal state have different values for this invariant, the goal is impossible.

Looking Ahead

Proof by contradiction is closely related to another indirect proof technique: proof by contrapositive. While they both rely on indirect reasoning, they have different logical structures and are suited for different types of problems. In our next lesson, we will explore the proof by contrapositive and see how to apply it to conditional statements in combinatorics.