Proof by Contradiction: Combinatorial Impossibilities

The Logic of "Reductio ad Absurdum"

The method of proof by contradiction, also known as reductio ad absurdum (Latin for "reduction to absurdity"), is built on a simple, powerful idea. To prove a proposition $P$ is true, we begin by assuming that it is false, i.e., we assume $\neg P$. We then follow the logical consequences of this assumption until we arrive at a contradiction—a statement that is undeniably false, like $1=0$ or "the number $n$ is both even and odd". Since our reasoning was sound, the only possible source of error must be our initial assumption. Therefore, we are forced to conclude that $\neg P$ is false, which means $P$ must be true.

The following video provides an excellent introduction to this line of reasoning.

To solidify the formal structure, let's turn to a written resource.

Classic Proofs by Contradiction

Before we dive into combinatorial problems, let's see this method in action with two famous proofs. Your background in number theory will be helpful here, as these examples deal with properties of integers and prime numbers.

The archetypal proof by contradiction is the proof that $\sqrt{2}$ is irrational.

Another beautiful example is Euclid's proof for the infinitude of primes. It shows that the set of prime numbers cannot be finite by assuming it is, and then constructing a new number that must have a prime factor not in the supposedly complete set.

These examples demonstrate the elegance of contradiction: instead of an exhaustive search or a complex construction, we use a single, clever assumption to show that an entire scenario is impossible.

Combinatorial Impossibility: Coloring Arguments

Now let's apply this technique to combinatorics, fulfilling this lesson's main learning outcome. A frequent task in Olympiad-level problems is to determine if a board can be tiled with certain shapes. Often, the answer is no, and proof by contradiction is the perfect tool to show why.

A powerful method for this is coloring. We assign colors to the squares of a board or elements of a set and analyze how the tiles or operations interact with the colors. If we assume a tiling is possible and that assumption leads to a conclusion that violates the properties of our coloring, we have found a contradiction.

Let's consider a classic problem:

Can a standard 8x8 chessboard with two opposite corners removed be tiled by 1x2 dominoes?

The following video gives a short, elegant, and visual proof by contradiction.

The logic is airtight:

1. Assumption: Assume the mutilated board can be tiled by 1x2 dominoes.
2. Coloring Analysis: A standard chessboard has 32 white and 32 black squares. The two opposite corners have the same color (e.g., white). Removing them leaves 30 white squares and 32 black squares.
3. Invariant Property: Each 1x2 domino, no matter where it's placed, must cover exactly one white square and one black square.
4. Contradiction: If the board were tiled by dominoes, the tiled area must contain an equal number of white and black squares. However, our board has an unequal number (30 white, 32 black). This is a contradiction.
5. Conclusion: Our initial assumption was false. The board cannot be tiled.

This coloring technique is not limited to two colors or simple checkerboard patterns. Some problems require more creative colorings to find the contradiction.

Let's look at a problem that uses a coloring argument in a slightly different way.

Practice Problems

It's time to put this technique into practice. As you work through these problems, remember the core structure: assume the opposite of the claim and work logically until you find an undeniable contradiction.

1. Number Theory Impossibility: Prove that there are no integer solutions to the equation $x^2=4y+3$.
   Hint: Assume a solution exists and consider the parity of $x$. What does this imply about the remainder of $x^2$ when divided by 4?

2. Grid Path Impossibility: A frog is jumping on an 8×8 chessboard. At each step, the frog jumps from one unit square to an adjacent square (one that shares an edge). Is it possible for the frog to start from the lower-left corner, visit each of the 64 squares exactly once, and finish at the upper-right corner?
   Hint: This is a question about a Hamiltonian path. Use a chessboard coloring. What color is the starting square? What color must the ending square be after 63 jumps?

3. Process Impossibility: The number 12 is written on a blackboard. Every minute, the number on the board is replaced by either multiplying it by 2 or 3, or dividing it by 2 or 3 (if divisible). Prove that the number on the board can never be 54 after exactly one hour (60 minutes).
   Hint: Write the numbers in their prime factorization, $2^a{3}^b$. Consider the parity of the sum of the exponents, $a+b$. What happens to this parity after one operation? What must the parity be after 60 operations?

4. Advanced Tiling: Can a 10×10 board be tiled with 1×4 rectangles?
   Hint: A standard 2-coloring (chessboard) is not sufficient here. Try coloring the board with four colors, say 0, 1, 2, 3. For example, color the square at row $i$ and column $j$ with the color $(i+j)(\mathrm{mod}4)$. How many squares of each color does a 1x4 tile cover? How many squares of each color are on the board?

Conclusion

Today, you've learned to wield one of the sharpest tools in a mathematician's arsenal: proof by contradiction. By assuming the opposite of what you wish to prove, you can expose hidden flaws and logical absurdities, allowing you to prove statements of impossibility with definitive clarity.

Key Takeaways:

• Structure: To prove $P$, assume $\neg P$ and derive a contradiction. To prove $P\to Q$, assume $P\wedge \neg Q$ and do the same.
• Application in Combinatorics: This method is ideal for proving that certain configurations are impossible. Problems involving tilings, paths, or processes are common candidates.
• Coloring Arguments: Coloring is a powerful technique used within a proof by contradiction to reveal an invariant that is violated by the assumed possibility of a tiling or process.

In our next lesson, we will explore the Extremal Principle. While contradiction often proves a negative (what can't be done), the extremal principle is a constructive method that helps us understand the properties of a system by examining its "smallest," "largest," or "most extreme" elements.