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.

image via Wikipedia

Proof

For the sake of contradiction, assume on the contrary that the person is an Idea island native.  Then we have two possibilities: the person is either a knight or a liar. If the person is a knight, he is not a liar, and because he always tells the truth, he cannot say “I am a liar.”  If the person is a liar, then he always lies and because his phrase “I am a liar” is true, he could not say it. Therefore, both cases are impossible, and we arrive at a contradiction, proving that the person is not an Idea island native.

Proof by contradiction (read more examples) is one of the methods of proof in higher mathematics.   Some of the popular methods are direct proof and mathematical induction.

Related Posts Plugin for WordPress, Blogger...

3 thoughts on “Proof by Contradiction: Knights and Liars

Leave a Reply