영포인트 님의 제안처럼 세번 연속 거짓말을 할 수 없다는 규칙으로 재구성하겠습니다. 질문자는 을로, 대답하는 사람은 갑이라 하지요.1부터 8까지의 숫자 가운데 갑이 8을 손바닥에 썼다 하고, 을은 이 숫자를 모르니 편의상 X라 하겠습니다. 그리고 참말은 T, 거짓말은 F로 표시하고 ‘네’는 Y로, ‘아니오’는 N으로 표시합니다.


먼저 갑이 세번 모두 참을 말하는 경우(T,T,T)부터 예로 들겠습니다. 을은 (1,2)의 집합 안에 X가 있냐고 묻고 갑이 참말로 대답합니다. 1과 2는 자신이 쓴 8(X)이 아니므로 참말은 N이 됩니다. 이것을 간단히 (1,2) → N(T) 라 하겠습니다.


마지막(이 경우에는 3번째)을 제외하면 그 이전의 모든 질문에 대해 을은 갑이 뭐라 하든 거짓으로 여긴다고 말씀드렸지요? 여기서도 을은 아니오(N)라는 갑의 대답을 거짓이라 규정하고 (1,2) 중에 X가 있을 것이라 생각합니다. 그래서 예컨대 1을 두번째 질문으로 합니다. 즉, X가 1이냐고 묻는 것이지요. 세번 모두 참을 말하는 경우를 가정했으므로 두번째 질문은 다음처럼 요약됩니다. (1) → N(T)


을은 이 역시 거짓이라 판단하므로 세번째 질문은 자연스럽게 X가 1이냐고 한번 더 묻는 형식이 될 것이고, 갑은 참말(N)을 대답합니다. 이것은 (1) → N(T) 로 쓸 수 있겠지요. 자, 이제 세번의 질문과 대답을 다시 옮겨보겠습니다.


1번째 질문과 대답 : (1,2) → N(T)
2번째 질문과 대답 : (1) → N(T)
3번째 질문과 대답 : (1) → N(T)


을은 1,2번째 질문을 거짓으로 생각했으므로 3번 연속 거짓말을 할 수 없다는 규칙을 기특하게 생각해내고는 3번째를 참말이라 판단합니다. 갑의 대답은 ‘1은 X가 아니다’는 것이므로 이 세번의 질문을 통해 을은 X의 후보에서 1을 제외할 수 있다는 것입니다.


언뜻 이해하기 힘들지만 ‘을이 갑의 대답을 무조건 거짓말로 단정지었다'는 방편에서 벗어나 숫자 1의 입장에서 복기를 해 보면 그나마 좀 쉽습니다. 위의 질문과 대답에서 뭔가 보이시나요? 세번의 대답에서 어쨌든 숫자 1은 모두 갑으로부터 N의 답을 받았습니다. 이것이 중요합니다. 갑이 세번 모두 N이라 답했다는 것은 N이 참말이라는 것을 의미하기 때문입니다. 세번 모두 거짓말일 수는 없으니까요. 그래서 우리는 이 세번의 질문(저는 1 Set라 이름붙였습니다만)의 결과, 1은 확실히 X가 아님을 알 수 있었고 후보에서 제외할 수 있다는 것입니다.


다른 Set를 볼까요? (F,T,T)인 경우입니다.
1번째 질문과 대답 : (1,2) → Y(F)
2번째 질문과 대답 : (3) → N(T)
3번째 질문과 대답 : (3) → N(T)


숫자 3의 입장에서 보겠습니다. 1번째에서 갑은 1과 2 가운데 X가 있다고 했으므로 3은 확실히 N이었고, 2번째와 3번째에서도 3은 N입니다. 갑에 의해 세번 모두 N을 받았으므로 3이 N인 것은 참말이 되겠지요. 여기서 우리는 3을 제외할 수 있습니다.


이런 Set를 충분하게 시행하면 하나씩 하나씩 후보에서 제외되는 숫자들이 나오고 남은 숫자들로 집합을 만들면 을은 반드시 이 게임에서 승리할 수 있습니다. 그렇다면 몇 개까지 줄일 수 있을까요?


이를 위해 규칙을 더 단순화하겠습니다. 숫자 1부터 4 사이에 X(4)가 있습니다. 두번 연속 거짓말을 할 수 없다는 것이 규칙입니다.


우선 (T,T)를 보겠습니다.
1번째 질문과 대답 : (1) → N(T)
2번째 질문과 대답 : (1) → N(T)


숫자1의 입장에서 보면 두번 다 N의 답을 받았습니다. 두번 연속 거짓을 말할 수 없으므로 1이 N인 것은 참말입니다. 즉, 1은 X가 아닙니다. 1을 제외하고 2,3,4 가운데 다시 하겠습니다. 이번엔 (F,T)로 해볼까요.


1번째 질문과 대답 : (3) → Y(F)
2번째 질문과 대답 : (2) → N(T)


숫자 2의 기준에서 보면 두 번의 질문에서 모두 N을 받은 셈이 됩니다. 둘 다 거짓일 수 없으므로 2가 N이라는 것은 참입니다. 즉 2를 제외할 수 있습니다. 이제 3,4가 남았습니다. 그런데 여기서 더 좁힐 수 없습니다. 왜냐하면 갑도 방어전략이 있기 때문입니다.


을이 먼저 3을 제시한 경우입니다.
1번째 질문과 대답 : (3) → N(T)
2번째 질문과 대답 : (3) → Y(F)
즉, 갑이 (T,F) 전략을 쓰면 우리는 3이 X인지 아닌지 알 수 없습니다. 세번째, 네번째 질문을 거듭하더라도 갑이 1,2번째 대답을 무한 반복하면 그만입니다.


갑의 (F,T)전략은 어떨까요.
1번째 질문과 대답 : (3) → Y(F)
2번째 질문과 대답 : (4) → Y(T)
마찬가지로 을은 3과 4가운데 무엇이 X인지는 알 수 없습니다. 그러므로 우리가 알 수 있는 것은, 을의 질문에 갑이 대답하는 경우에 따라 1,2,3 중에 하나의 수와 정답인 4를 포함하는 (원소가 2개인) 집합을 만들 수 있다는 것입니다.


숫자가 3개 이상 남았을 때는 다른 질문을 충분히 하면서 줄이는 것이 가능하지만 2개 남았을 때는 불가능합니다. 이렇듯 연속된 2번의 질문이면 원소 2개까지 압축할 수 있습니다. 질문의 횟수가 늘어날 때마다 2의 거듭제곱으로 압축가능한 원소의 숫자가 늘어나므로 3번의 질문이면 원소 4개, 4번이면 원소 8개, 원래 문제였던 9번의 질문이면 원소 256개인 집합을 제시하여 을이 승리하게 됩니다. 앞서 말씀드렸듯이 이것은, 총질문이 m회라면 정답이 포함된 집합의 원소 수의 최솟값이 2^(m-1)임을 뜻합니다.


이제 영포인트 님의 질문에 답할 차례입니다. 저는 첫 질문으로 2개의 숫자를 말씀드리고 영포인트 님의 질문이 거짓이라 잠정적으로 판단한 후 두 번째 질문으로 1개의 숫자를, 같은 식으로 1개의 숫자로 세번째 질문을 할 것입니다. 최종적으로 4개의 숫자까지 좁힐 수 있습니다.