Proof by Contradiction: Knights and Liars

I am currently reading a local book about mathematical problem solving and I came across with a cute proof demonstrating proof by contradiction.  Actually, I heard a very similar problem ages ago, but I never really thought that it was mathematical and never really bothered to solve it.

Anyway, according to the authors, the problem was based on the lectures given by Oleg Goldberg (an International Math Olympiad gold medalist) at the IDEA MATH program, a weekend extracurricular training on problem solving [in Massachussettes?].  The problem and proof are as follows.

Problem

All natives of the Idea island are either knights or liars. Knights always tell the truth, and liars always lie.  A person says “I am a liar.” Prove that he is not an Idea native.

Note: The idea of putting the image below is to let you do the proof first before scrolling down.  So, no peeking please. » Read more

Proof that log 2 is an irrational number

Before doing the proof, let us recall two things: (1) rational numbers are numbers that can be expressed as \frac{a}{b} where a and b are integers, and b not equal to 0; and (2) for any positive real number y, its logarithm to base 10 is defined to be a number x such that 10^x = y. In proving the statement, we use proof by contradiction.

Theorem: log 2 is irrational

Proof:

Assuming that log 2 is a rational number. Then it can be expressed as \frac{a}{b} with a and b are positive integers (Why?).  Then, the equation is equivalent to 2 = 10^{\frac{a}{b}}. Raising both sides of the equation to b, we have 2^b = 10^a. This implies that 2^b = 2^a5^a.  Notice that this equation cannot hold (by the Fundamental Theorem of Arithmetic) because 2^b is an integer that is not divisible by 5 for any b, while 2^a5^a is divisible by 5. This means that log 2 cannot be expressed as \frac{a}{b} and is therefore irrational which is what we want to show.

More examples of proof by contradiction

We have had good discussions on mathematical proofs, so I am planning to create a mathematical proof series that will discuss the basics such as direct proof, indirect proof, and proof by mathematical induction.  But before I do that, let me continue with more examples of proof by contradiction.

Proof by contradiction, as we have discussed, is a proof strategy where you assume the opposite of a statement, and then find a contradiction somewhere in your proof. Finding a contradiction means that your assumption is false and therefore the statement is true. Below are several more examples of this proof strategy.

Example 1:  \sqrt{2} irrational.

Example 2: \sqrt{6} is irrational. The proof of this is basically the same as example 1, so it is left as an exercise.

Example 3: Proof that there are infinitely many primes.

Example 4: Knights and Liars

Example 5: \sqrt{2} + \sqrt{3} is irrational. » Read more

Related Posts Plugin for WordPress, Blogger...
1 2