폴리매스

 어떤 마을 사람들은 논리적인 질문에만 예, 또는 아니오로 답한다고 한다. 마을 사람들 중에는 모든 질문에 거짓으로만 답하는 거짓말쟁이와 참으로만 말하는 참말쟁이가 있다. 이 마을에 관광 온 당신은 길을 물어보기 위해 이 둘을 구별하려고 한다.

 (1) 거짓말쟁이를 구분할 수 있는 질문을 제시하시오. 

 당신이 다녀간 후, 들킨 것에 자존심이 상한 거짓말쟁이들은 머리를 굴리기 시작했다. 마을의 거짓말쟁이들은 똑똑한 순서대로 음이 아닌 정수 값의 IQ를 받았는데, IQ 0인 거짓말쟁이는 머리가 나빠서 원래대로 답한다. 하지만 이제 IQ 1인 거짓말쟁이들은 더 머리를 굴려서 IQ 0인 거짓말쟁이를 구별해낼 수 있는 질문에만 참말로 답한다. 마찬가지로 계속돼, IQ n인 거짓말쟁이들은 IQ (n-1)인 거짓말쟁이를 구별해낼 수 있는 질문에 참말로 답한다. 거짓말쟁이들이 이렇게 머리를 굴린 뒤 당신이 돌아와 다시 길을 물어보려고 한다.

 (2) IQ가 몇인 거짓말쟁이부터 구분할 수 없을까? 모든 거짓말쟁이들을 구분할 수 있을까?

 모든 질문에는 증명을 포함해 답하라.  * 친구가 만든 문제로, 허락을 받고 올립니다.