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.
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.
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.