Proof by contradiction

Proof by contradiction is a frequently used method in proof. If the original proposition is , proof by contradiction or indirect proof first assumes that the opposite proposition is true and then shows that the opposite proposition leads to a contradiction. Thus, the proposition must be true.

Irrational number: Can you prove that 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 classic example of proof by contradiction. If is not an irrational number, it can be expressed as the 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. Thus, we will have a pair of m and n that have no common factors. It is called an irreducible fraction. Since , we have . Thus, must be an even number and must be an even number as well. Let’s express as , where x is an integer, since m is even. Then and we have , which means must be even as well. But if both and are even, that contradicts the earlier statement that and have no common factors. Therefore, must be an irrational number.

Prove the theorem that there are infinitely many prime numbers.

Solution: Assume that there are a finite number of prime numbers and let be the largest prime number. The list of all prime numbers is . Let be the product of all prime numbers plus 1, . From the equation, we know that leaves a remainder of 1 upon division by Thus, is not divisible by any (other) prime numbers and must be a prime number itself. Since and is a prime number, we have a contradiction. Therefore, there are infinitely many primes.

Suppose is a composite integer. Prove that has a prime factor less than or equal to .

Solution: Since is a composite integer, we can find two integers and such that where If has no prime factor that is less than or equal to then and If and we have which contradicts Therefore, has a prime factor less than or equal to .

««« Rainbow hats: Seven prisoners are given a chance to be set free tomorrow. A warden 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 warden’s discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form. Then each prisoner writes down the 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 serve their remaining sentences.

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?[23]

Solution: To solve this problem, it requires some out-of-the-box thinking. The hint gives a possible way of approaching the problem. Once you realize that if we code the colors to 0-6, 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 so that the sum of and the rest of 6 prisoners’ hat color codes will give a remainder of i when divided by 7, where is a unique number between 0 and 6. For example, prisoner 0’s guess should make . This way, we can guarantee at least one of for .

We can prove this conclusion by contradiction. If , then (since and and are both between 0 and 6). But if for all and 6, then , which is clearly impossible. So at least one of must equal to . As a result, using this strategy, they are guaranteed to be set free.