어떤 공식을 동원하는 문제는 아닌 것 같아서, 그리고 출제자의 의도와도 부합하는 것 같아서 그냥 논리로만 풀어보았습니다(문과 출신이니 공식을 도출해서 풀 능력도 안 됩니다). 워낙 까다로운 문제인 만큼 바로 풀이 과정을 밝히는 것보다는 제가 문제를 더듬어 간 과정을 소개하는 것이 독자의 이해를 위해서는 나을 것 같습니다(사실 정답이란 믿음도 크지 않습니다).

문제에는 '9번 연속', '256'이라는 힌트가 등장합니다. 당연히 저는 2의 거듭제곱이 문제 풀이의 유력한 단서임을 암시한다고 생각했습니다(참말과 거짓말이라는 구분도 2를 떠올리게 하지요). 그리고 정답인 특정 숫자를 맞히는 것이 아니라 그 특정 숫자를 포함, 256개의 원소로 이루어진 집합을 구성하라는 것이 출제자의 요구이므로 9번과 256 사이의 관계를 밝히면 적어도 문제가 절반 이상 해결된 것이나 다름 없다는 확신이 들었습니다 (여기까지는 많은 분들이 도달하셨을 것입니다).

그런데 가장 큰 어려움은 '9번 연속 거짓말을 할 수는 없다'는 규칙에 있습니다. 상대가 9번 가운데 언제, 몇 번이나 거짓말을 할 것인지 막막하다는 것입니다. 그렇다면 결국 상대로 하여금 막다른 골목까지 계속 거짓말을 하도록 유도해 내는 것이 이 문제의 열쇠라는, 즉 참말은 반드시 9번째에 최초로 등장해야 한다는 결론이 나옵니다. 몇 번을 생각해도 여기까지는 오류가 없어 보였습니다.

하지만 무슨 수로 상대가 거짓말을 하도록 유도할까요? 저는 상대가 참말을 하든 거짓말을 하든, 거짓말을 하고 있다고 가정하고 다음 질문으로 넘어가면 어떨까 생각했습니다. 그러니 앞선 8번의 대답이 모두 거짓이라고 가정할 수 있는 장치를 고안하는 것이 중요할 수밖에 없습니다. 그 설계도는 다음과 같습니다.

가령 첫 질문으로, 1부터 1000까지의 수 가운데 짝수 500개를 선택해서 정답이 이 안에 있냐고 물었다고 하지요. 상대는 참말, 거짓말을 아무렇게나 할 수 있습니다. 다만 상대의 대답을 무조건 거짓이라고 판단하고 2번째 질문을 한다는 것과, 2번째 질문에서는 500개가 아니라 250개로 줄여서 질문한다는 점이 제 착안의 핵심입니다.

상대가 네라고 하면 2번째 질문에서는 홀수 가운데 250개를 선택하고, 상대가 아니오라고 하면 계속 짝수 가운데 250개를 선택한다고 보시면 됩니다. 이 과정에서 상대의 첫번째 답변은 거짓으로 '유도'됩니다. 이것을 반복하다 보면 마지막 질문을 통해 정답이 아닌 숫자를 제외할 수 있습니다. 그러니까 정답 후보를 형성해나가는 것이 아니라 확실히 정답이 아닌 숫자들을 없애나가는 것이 제가 접근한 방식이었습니다.

저는 여러 차례의 시행 착오를 겪으면서 첫 질문에서 선택해야 하는 숫자들이 128개라고 생각했습니다. '256=2^8'이고 어차피 9번째 질문은 참말이 되어야 하므로 256개로 시작을 했으나 실패, 512와 128로 풀어본 결과 128이 논리적이었습니다. 이제 풀이 과정입니다.

1. 1번째 질문 : 1부터 1000까지의 숫자 가운데 아무 거나 128개의 숫자를 고른 다음 이 안에 네가 고른 숫자가 있냐고 물어봅니다 (내심 상대가 뭐라 대답하든 우격다짐, 막무가내로 거짓이라 여길 작정입니다).

2. 2번째 질문 : 1번째 질문에 대해 상대가 네라고 하면 애초의 128개를 제외한 872개의 숫자 가운데에서, 상대가 아니오라고 하면 원래 128개에서 64개의 숫자를 골라서 이 안에 네가 고른 숫자가 있냐고 묻습니다.

3. 3번째 질문 : 같은 패턴으로 상대가 네라고 하면 64개를 제외한 숫자 가운데에서, 상대가 아니오라고 하면 원래 64개에서 32개의 숫자를 골라서 마찬가지로 묻습니다.

4. 7번째 질문 : 이런 식으로 진행하면 2개의 숫자를 골라서 7번째 질문을 하게 됩니다. 이에 대해 상대가 네라고 하면 2개를 제외한 숫자 가운데에서, 상대가 아니오라고 하면 원래 2개에서 1개의 숫자를 골라 묻습니다 (8번째 질문).

5. 8번째 질문에 대해 상대가 네라고 하면 그 숫자를 제외한 숫자 하나를, 아니오라고 하면 그 숫자를 가지고 마지막 9번째 질문을 합니다. 8번의 질문에서 모두 거짓을 답한 것으로 설계했기 때문에 9번째 대답은 참말로 '간주'할 수 있습니다. 9번째 질문에서 상대가 아니오라고 하면 그 숫자는 정답에서 제외됩니다. 9번의 질문을 통해 정답이 아닌 숫자 1개를 발견한 것입니다(이 9번의 질문을 편의상 한 set라 부르겠습니다). 숫자를 달리해 가며 충분한 횟수의 set를 시행하면 한 번의 set마다 하나씩 정답이 아닌 숫자들을 제외시킬 수 있습니다 (set의 9번째 질문에서 네라고 하면 그 숫자를 제외하고 다음 set로 넘어갑니다. 256개의 후보 풀을 구하는 것이므로 다음 set의 9번째 질문을 통해 제외되는 숫자와 중복되지만 않으면 됩니다. 실제로 중복되지 않습니다).

6. 그럼 몇 개까지 후보군을 줄일 수 있을까요? 최초에 등장했던 9번 연속과 256이라는 힌트가 여기서 쓰입니다. 8번 연속 거짓말을 할 수 있고 (하게 만들고) 9번째 질문을 통해서 하나의 숫자를 제외할 수 있으므로 2의 8제곱인 256개까지는 set 시행 횟수만 충분하다면 가능합니다 (역으로 8번 연속 거짓말을 할 수 있으므로 256개 미만으로는 줄일 수 없다는 의미이기도 합니다).

7. 이것은 일반화가 가능한데 예를 들어 '두 번 연속 거짓을 말할 수는 없다'는 것으로 문제를 고치면 2개의 숫자로 후보를 줄일 수 있고, '세 번 연속 거짓을 말할 수는 없다'라면 4개의 후보들로 압축할 수 있습니다. '네번'이면 8개, '다섯번'이면 16개가 되겠지요. 즉, x번 질문을 한다고 했을 때, 정답이 포함된 집합의 원소 수의 최솟값은 2^(x-1)로 정리됩니다.