2.9 Proof by Contradiction

In a proof by contradiction or indirect proof, you show that if a proposition were false, then some logical contradiction or absurdity would follow. Thus, the proposition must be true.

Irrational number

Can you prove that $\sqrt2$ is an irrational number? A rational number is a number that can be expressed as a ratio of two integers; otherwise it is irrational.

Solution: This is a classical example of proof by contradiction. If $\sqrt2$ is not an irrational number, it can be expressed as a ratio of two integers $m$ and $n$. If $m$ and $n$ have any common factor, we can remove it by dividing both $m$ and $n$ by the common factor. So in the end, we will have a pair of $m$ and $n$ that have no common factors. (It is called irreducible fraction.) Since $m/n=\sqrt2$, we have $m^2=2n^2$. So $m^2$ must be an even number and $m$ must be an even number as well. Let’s express $m$ as $2x$, where $x$ is an integer, since $m$ is even. Then $m^2=4x^2$ and we also have $n^2=2x^2$, which means $n$ must be even as well. But that both $m$ and $n$ are even contradicts the earlier statement that $m$ and $n$ have no common factors. So $\sqrt2$ must be an irrational number.

Rainbow hats

Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner’s head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner’s discretion. Every prisoner can 32 see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed.

They are given the night to come up with a strategy. Is there a strategy that they can guarantee that they will be set free? ¹⁹

Solution: This problem is often perceived to be more difficult than the prisoner problem in the modular arithmetic section. In the previous prisoner problem, the prisoners can hear others’ guesses. So one prisoner’s declaration gives all the necessary information other prisoners need. In this problem, prisoners won’t know what others’ guesses are. To solve the problem, it does require an aha moment. The key to the aha moment is given by the hint. Once you realize that if we code the colors to 0-6, $\displaystyle\left(\sum_{i=1}^7x_i\right)\%7$ must be among 0, 1, 2, 3, 4, 5 or 6 as well. Then each prisoner $i$—let’s label them as 0-6 as well—should give a guess $g_i$ so that the sum of $g_i$ and the rest of 6 prisoners’ hat color codes will give a remainder of $i$ when divided by 7, where $g_i$ is a unique number between 0 and 6. For example, prisoner 0’s guess should make $\displaystyle\left(g_0+\sum_{k\ne0}x_k\right)\%7=0$. This way, we can guarantee at least one of $g_i=x_i$ for $i=0,1,2,3,4,5,6$.

We can easily prove this conclusion by contradiction. If $g_i\ne x_i$, then $\displaystyle\left(\sum_{i=1}^7x_i\right)\%7\ne i$ (since $\displaystyle\left(g_i+\sum_{k\ne i}x_k\right)\%7\ne i$ and $g_i$ and $x_i$ are both between 0 and 6). But if $g_i\ne x_i$ for all $i=0,1,2,3,4,5,$ and 6, then $\displaystyle\left(\sum_{i=1}^7x_i\right)\%7\ne0,1,2,3,4,5,6$, which is clearly impossible. So at least one of $g_i$ must equal to $x_i$. As a result, using this strategy, they are guaranteed to be set free.