얼마나 많은 분들이 흥미로우실지는 모르겠지만, 제 생각에 대한 여러분 의견도 듣고 싶고


혹시 궁금해 하시는 분들이나 풀고계시는 분들에게 자극이 되길 바라며 올려봅니다.


아래는 문제 입니다.




문제 상황을 요약하자면,


- 총 수감자는 100명이고, 이들 모두는 녹색 눈을 가졌다.

- 각 수감자는 스스로의 눈이 녹색인지 아닌지 알 수 없지만, 다른 99명의 눈 색은 녹색임을 알고 있다.

- 각 수감자는 서로 어떤 정보 공유도 할 수 없다.


Q. 각 수감자에게, 스스로의 눈 색이 녹색임을 확신시킬 수 있는 한 문장을, 수감자들에게 어떠한 새로운 정보도 제공하지 않도록 제시하시오. 



A. 일단 다음의 "적어도 한명은 녹색 눈이다" 라는 명제에서 출발해보죠.

 

N=2 일때는 정확히 이 명제로 해결 가능합니다. 각 수감자는 이 명제를 듣는다고 해서 그날 밤 석방 요구를 하지는 않을 겁니다. 왜냐면, 이미 상대방 눈이 녹색이라는 걸 봐서 알고 있고, 내 눈색에 대한 어떤 정보도 담겨있지 않기 때문입니다. 즉, 각 수감자는 (내가 남아있다 <=> 상대방 눈이 녹색) && (상대방이 남아있다 <=> 내 눈이 녹색) 가 되므로 두 수감자 모두 녹색 눈이라는 결론에 도달하고, 두 수감자 모두 석방 요청을 하게 되겠죠.


그러나 N=3 인 경우엔, "적어도 한명은 녹색 눈이다" 로는 부족합니다. 똑같이 각 구성원은 다른 두 명의 눈이 녹색이라는 것을 관측하고, 석방 요구를 하지 않겠지만 그 사실만으로는 내가 녹색이 아니라는 가능성을 부정할 수는 없습니다. N=2 일때와 같은 방법으로 해결되려면 "세명 중 적어도 두명은 녹색 눈이다" 라는 명제가 필요하죠.


눈치가 빠르신 분들은 이쯤 되면 일반화를 하셨을 겁니다. 즉, N명의 경우 적어도 N-1명은 녹색 눈이다 라는 명제를 제공해주면, 모든 수감자들은 N-1명의 녹색 눈들을 관찰하고 있기 때문에 이 명제만으론 자신이 녹색이 아닐 가능성을 배제할 수 없어서 석방을 시도하지 않을 것이고 모두가 남아있는 그 결과가 역설적으로, N명 모두 녹색 눈이라는 사실을 증명하는 것이 됩니다.


그러나 동시에, '어라? 뭔가 이상하다' 라고 생각하는 분이 계실 수 있습니다. 수감자들은 매일 서로를 세며 N-1명이 녹색 눈임을 확인하고 있는데, 결국 위 명제는 아무런 정보도 주지 않는 것이 아닌가? 도대체 뭐가 다른걸까?


이 문제의 핵심은, 수감자들끼리 서로 갖고 있는 정보를 교환할 수 없다는 점 입니다. 수감자들은 매일 수감자의 수를 세며 서로의 모습을 보고있고, 100명 중 자신을 제외한 적어도 99명의 수감자는 눈이 녹색이라는 사실을 알 고 있지만 다른 수감자들도 녹색 눈을 가진 사람이 99명이라는 사실을 알고 있는지는 모릅니다. 그러나 우리가 "적어도 99명의 사람은 녹색 눈입니다" 라는 아무런 정보도 담고 있지 않는 말하는 순간, 모두가 같은 정보를 공유하게 되고 비로소 다른 수감자의 행동의 이유를 추론할 수 있게 됩니다. (ex. 어라? 아무도 탈출 안했네? 아하, 얘네 눈에는 모두 스스로를 제외한 99명이 녹색 눈이구나. 그렇다면 즉 우리 모두 다 녹색 눈이구나!) 서로가 가진 정보를 교환할 수 없다는 점에서 일종의 죄수의 딜레마 와 같은 상황이라고 볼 수 있겠네요.


엄밀하게는 N명의 경우의 일반화에 대한 귀납적 증명이 붙어야 하겠지만, 여백이 부족하여 생략하겠습니다. 총총총