proof by contradiction Archives - Math and Multimedia

Proof by Contradiction: Knights and Liars

January 19, 2012 GB College Mathematics, High School Mathematics

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

3 comments knights and liars, mathematical proofs, methods of proof, proof by contradiction, proof by contradiction example

Proof that log 2 is an irrational number

January 6, 2012 GB High School Mathematics, High School Number Theory

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.

One comment irrational numbers, log 2, proof by contradiction, rational numbers

More examples of proof by contradiction

July 1, 2011 GB High School Geometry, High School Mathematics, Problem Solving and Proofs

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.