d라이브러리

중·고교 교과과정의 수학을 넘어서지 않는 수준에서 해결할 수 있는 재미있는 수학 연구 주제를 소개합니다. 수학을 연구하는 태도를 갖는 것은 사실 별로 어려운 것이 아닙니다. 수학적인 호기심에따라 ‘이러면 어떨까, 또 저러면 어떨까’라고 질문하고 답을 열심히 찾으면 되는 겁니다. 수학동아의 독자들 중에서 한국의 가우스나 오일러가 될 학생이 틀림없이 나올 거라 기대하면서, 첫 번째 연구 주제를 제시합니다. 2005년에 KAIST 사이버영재교육센터에서 실제로 출제됐던 과제로, 거짓말이 포함된 스무고개에 관한 아주 흥미로운 주제랍니다. 풀이는 2월 1일 수학동아홈페이지(math.dongascience.com)에서 확인하세요!


영재캠프에 참가한 32명의 학생에게 각각 1번부터 32번까지의 출석번호가 부여됐다.
은용이 자기 번호를 기억하지 못해서 선생님께 번호를 다시 알려달라고 부탁한다.
은용 “선생님, 제가 번호를 까먹었어요. 다시 좀 알려주실래요?”
선생님 “아아 그래? 은용이 번호는…. 음, 그냥 가르쳐주면 재미없지! 우리 번호 맞히기 놀이 하자!”
선생님께서 제안한 번호 맞히기 놀이는 다음과 같다. 은용이 선생님께 질문하면, 선생님은 ‘예’ 또는 ‘아니오’로만 대답하기로 한다. 은용은 이렇게 질문을 몇 번 한 뒤 자기번호를 알아맞혀야 한다.
선생님 “다섯 번 안에 맞히면 아이스크림을 사주마.”
은용 “다섯 번? 좋아요, 자신 있어요!”

범위 안의 어떤 번호든 n번 이하의 질문으로 항상 알아내는 질문방법이 있으면 n번으로 알아낼 수 있다고 하자. 반면 n번 이하의 어떤 질문방법으로도 범위 안에서 알 수 없는 번호가 항상 있다면 n번으로 알아낼 수 없다고 하자.
 

조금 있으니 이번에는 주영이가 선생님을 찾아왔다.
주영 “선생님, 저도 번호를 잊어버렸어요.”
선생님 “하하하, 주영이도 번호 맞히기 놀이를 하자!”
은용 “풋! 주영아, 이렇게 물어보면 다섯 번이면 돼.”
주영 “앗! 고마워, 은용아.”
선생님 “은용이 뭐야. 재미없어지잖아. 좋아 그럼, 선생님은 이번엔 조건을 걸겠어!”
은용과 주영 “네? 무슨 조건요?”
선생님 “너희가 질문하면 나는 거짓말 대답을 딱 한 번은 할 수 있는 것으로 하자.”
은용과 주영 “으악! 너무 어려워요, 선생님!”
선생님 “후훗, 그래도 알아맞힐 수는 있겠지?”
주영 “음, 네. 할 수 있을 것 같아요. 질문은 ‘예, 아니오’를 묻는 것이면 뭐든지 다 되나요? 그러니까 예를들어, 같은 질문을 또 해도 되나요?”
선생님 “와, 주영이가 벌써 핵심을 찌르네? 응, 그런 질문이면 뭐든지 다 돼. 다만 선생님한테 미래를 미리 결정하도록 요구하는 질문만 빼고. 예를 들어 ‘다음 질문에서 거짓말을 할 것인가’하는 등의 질문은 허용되지 않아.”
주영 “네, 그럼 열한 번이면 할 수 있겠는데….”
선생님 “그렇지? 역시 주영이야. 열 번 이내에 알아맞히면 아이스크림을 사주마.”
주영 “열 번은 어려울 것 같은데…, 아이스크림은 좋지만 거짓말은 싫어요!”

문제2
(1) 주영이가 11번의 질문으로 번호를 알아내는 방법을 찾아라.

(2) 주영이가 10번의 질문으로 번호를 알아내는 방법을 찾아라.


은용 “선생님, 혹시 아홉 번으로도 되나요?”
선생님 “응, 아홉 번까지는 방법이 있단다.”
주영 “아홉 번이요? 너무 어려워요.”
선생님 “내가 힌트가 되는 문제를 하나 알려주마.”

선생님께서 알려준 문제는 수 카드로 상대방이 생각한 수를 알아맞히는 것으로 다음과 같다. 먼저 1에서 8까지의 자연수 하나를 상대방이 생각해 정하도록 한다. 그리고 다음의 세 장의 카드를 한번씩 보여주고 여기에 그 수가 있는지 물어본다.
 

그러면 이 대답을 듣고 항상 상대방이 생각한 수를 알아맞힐 수 있다고 한다. 어떻게 된 것일까?
 

은용 “이야, 이런 방법이 있었다니…. 선생님, 그럼 여덟 번으로도 되나요?”
주영 “아홉 번도 이렇게 어려운데…. 여덟 번은 안 되지 않을까, 은용아?”
선생님 “응, 여덟 번으로는 불가능하단다.”
주영 “역시 그렇구나. 그런데 선생님, 불가능하다는 것은 어떻게 알아요?”
은용 “정말 궁금하네…. 질문방법은 무궁무진할 텐데 모든 방법을 다 따져볼 수도 없을 거고 이런 불가능성을 어떻게 확실히 말할 수 있죠?”
선생님 “후훗, 수학의 위대함이지. 앞서 1번 문제의 (2)에서도 우리는 이미 경우의 수를 비교하는 것으로 불가능성을 말한 적이 있다는 것을 기억하렴.”
은용 “네, 이건 어렵지 않았어요. 하지만 이번에는 상황이 다르잖아요. 거짓말 때문에 대답이 달라지고 질문도 더 많이 해야 하고…. 경우의 수를 도대체 어떻게 셀 수 있다는 건지 전혀 감이 오지 않아요.”
주영 “맞아요. 질문 여덟 번이면 대답은 모두 256가지. 32를 훨씬 넘잖아요.”
선생님 “질문방법은 너희가 생각하는 것이지만 거짓말은 나의 권리란다. 내가 거짓말을 언제 할지 선택할 수 있다는 것에 주목해보렴.”
주영 “아, 그렇다! 뭔가 떠올라요.”
은용 “그러니까 번호와 함께 언제 거짓말을 하는지도 경우를 따질 때 함께 세어야 한다는 것인가요? 하긴 똑같은 질문을 해도 거짓말을 언제 하느냐에 따라 돌아오는 대답이 여러 가지로 나뉘겠군요.”
주영 “그리고 우리가 번호를 알아냈다면 거짓말이 언제였는지도 당연히 알아야 하는 거네요.”
선생님 “역시! 선생님이 더 가르칠 게 없구나.”