11월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
퍼즐 정답자는 ‘김형섭’님으로 선정하였으며
HORIZON에서 준비한 선물을 전달해 드릴 예정입니다.
당신이 색깔을 반대로 말한다는 것은 어떤 정보의 참/거짓을 반대로 알려주는 것이다. 즉, 선량한 로봇들은 당신이 말한 정보에 의존적이도록, 사악한 로봇들은 당신이 말한 정보에 의존적이지 않도록 전략을 짜는 것이 핵심이다. 이렇게 하면 선량한 로봇들은 당신의 거짓말에 속아서 자신의 등 색깔을 반대로 추론하게 될 것이고, 사악한 로봇들은 당신의 거짓말과 상관없이 자신의 등 색깔을 정확히 추론하게 될 것이다. 물론 주인공인 당신은 다른 로봇들이 모두 진실을 말했다는 것을 알고 있으니 등 색을 쉽게 추론할 수 있을 것이다. 이렇게 로봇들의 추론 과정에 훼방을 놓으려면 정보들을 서로서로 연결해서 당신이 말한 정보가 로봇들의 추론 과정에 들어가도록 만들 필요가 있다. 다음과 같은 기본 전략을 생각하자.
● 모든 로봇은 자신 양옆에 있는 두 로봇의 등 색깔이 같으면 검정, 다르면 하양을 외친다.
이 정보는 모든 로봇이 들을 것이다. 가장 먼저 말한 로봇을 1번이라 하자. 그러면 1번은 2번과 9번의 색이 같은지 다른지를 알려줄 수 있다. 이런 관계를 정리하면 아래 그림과 같이 정보가 서로서로 이어진다. 99명을 다 그리기에는 너무 많으므로 9명으로 줄여서 그려 보자.
위 그림을 펼쳐서 보기 쉽게 다시 그리면 아래와 같다. 전체 로봇 수가 홀수이기 때문에 사이클이 2개로 나누어지지 않고 하나의 원형으로 이어진다.
이제 각 로봇은 자신의 오른쪽에 있는 로봇의 등 색깔을 알기 때문에 자신의 등 색깔도 추론할 수 있다. 가령 1번 로봇은 2번 로봇의 등 색깔을 알기 때문에, 4번 로봇의 등 색깔도 알고, 6번 로봇의 등 색깔도 알고, 8번 색깔의 등 색깔도 알고, 최종적으로 1번 자신의 등 색깔도 알 수 있게 되는 것이다. 다시 말해, 자신의 등 색깔은 2-4-6-8-1 경로에 “하양”이 짝수 번 외쳐졌으면 2번과 같은 색깔이고, “하양”이 홀수 번 외쳐졌으면 2번과 반대 색깔이다.
그런데, 이렇게 자신의 등 색깔을 추론해 내는 방법에는 2가지가 있다. ① 2-4-6-8-1의 경로를 거쳐도 되고, ② 2-9-7-5-3-1의 경로를 거쳐도 된다. 둘 중 무엇을 택하든 누군가 거짓말을 하지 않는 이상 필승전략이 맞다. 이를 그림으로 표현하면 다음과 같다.
자신의 양옆에 있던 로봇들이 위와 같은 정보 사이클에서는 정반대 편에 있게 된다. 위 그림을 보면 1번의 정반대 편에는 9번과 2번이 있고, 3번의 정반대 편에는 2번과 4번이 있다. 따라서, 어떤 로봇 입장에서 생각해도 경로 ①은 항상 왼쪽 절반을, 경로 ②는 항상 오른쪽 절반을 덮는다. 그리고 경로 ①과 ②를 더하면 9개의 정보 모두를 사용한다. 그리고 이 9개의 정보 중 하나는 당신이 말한 정보다.
거의 모든 준비가 끝났다. 이제 선량한 로봇들과 사악한 로봇들에게 이렇게 말해 두면 된다.
●선량한 로봇에게 : 자신 오른쪽에 있던 로봇의 등 색깔을 기준으로 자신의 등 색깔을 추론하되, 당신이 말한 정보를 거치는 경로를 선택하여 추론하여라.
● 사악한 로봇에게 : 자신 오른쪽에 있던 로봇의 등 색깔을 기준으로 자신의 등 색깔을 추론하되, 당신이 말한 정보를 거치지 않는 경로를 선택하여 추론하여라.
물론 오른쪽 대신 왼쪽에 있던 로봇의 등 색깔을 기준으로 삼으라고 말해도 된다. 이렇게 하면 선량한 로봇들은 당신이 말한 정보에 의존적이므로 자신의 등 색을 반대로 알게 될 것이고, 사악한 로봇들은 당신이 말한 정보에 의존적이지 않으므로 자신의 등 색을 정확히 알게 될 것이다. 이제 세계를 정복할 시간이다! (사악한 웃음)
다음은 11월의 정답자로 선정된 김형섭님의 해설입니다.
전략을 3단계로 나눠 설명해 보았습니다.
1. 샤우팅 전략
로봇 자신 기준 양측 로봇의 등 색깔이
— 같으면 “하양!”
— 다르면 “검정!”이라고 외친다.
2. 자기 등 색깔 알기 전략 (독방에서)
각 로봇은 다음 제시되는 과정을 통해 자기 등 색깔을 알 수 있다. 각 로봇은 모든 로봇의 “위치 정보”와 “외침 정보”를 기억한다. 이 전략은 좌측부터 시작할 수도 있고 우측부터 시작할 수도 있다.
(1) ‘우측부터 시작하기’의 경우
— 각 로봇은 자신 기준 우측 1번째 위치한 로봇의 등 색깔을 안다.
— 우측 2번째 ‘위치한 로봇의'(이후 생략) 외침도 기억한다.
— 2번째 외침은 샤우팅 전략에 따라 1번째, 3번째 등 색깔을 통해 결정되었다.
— 따라서 1번째 등 색깔과 2번째 외침을 통해 3번째 등 색깔을 알 수 있다.
(예를 들어, 1번째 등 색깔이 하양이고 2번째 외침이 “하양!”이라면 3번째 등 색깔은 하양임을 알 수 있다.) 각 로봇은 자신 기준으로 우측 2n+1 번째(n은 자연수) 등 색깔을 모두 알 수 있다. 99번째 등 색깔(n=49)은 바로 자신의 등 색깔이다.
(2) ‘좌측부터 시작하기’의 경우
–동일하다.
이렇게 자신의 등 색깔 아는 방법은 두가지가 된다.
3. 세계 정복 전략
위 방법은 내가 거짓말을 안 했을 때만 문제없이 작동한다. 내가 거짓말을 하는 순간 문제가 생긴다. 위 방법은 거짓말 없이는 둘 다 정답이지만 거짓말을 하면 하나는 오답이 되는 구조다. 좌측이든 우측이든 한쪽 방법은 위 계산 과정에서 반드시 나의 외침 정보를 반영하기 때문이다. 이 사실 때문에 거짓말을 했다고 가정하고 좌측이든 우측이든 그 방향이 나의 외침 정보를 반영했다면 거짓말이 반영된 셈이기 때문에 반드시 오답이다. 그 반대 방향을 통해 구하면 나의 외침 정보를 거치지 않아서 반드시 정답이다.
이제 선량한 로봇에게 오답을 말하게 하고 사악한 로봇은 정답을 말하게 하자. 다음을 지시한다.
(1) 선량한 로봇에게 나의 외침 정보가 반영된 방향으로 자신의 등 색깔을 구하라고 지시한다.
(2) 사악한 로봇에게는 반대로 하게 한다.
거짓말 없이는 문제없는 필승전략이기 때문에 지시(세계 정복 전략)가 이상해 보여도 로봇들은 의심 없이 전략을 따르게 된다.
