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