어디선가 본것인지 저장되어있길래 이렇게 올립니다.
어쩌면 뒷북일수도 있곘군요.. 그래도 재밌게 봐주세요.
어느 교도소에 죄수 23명이 있고
어느 한 방에(어떤 변화도 알수 없는 즉 그 용도를 모르는)
스위치 ⓐ와 ⓑ 두개가 있습니다.
그 스위치의 처음 상태는 교도소장만 알고 있습니다.
둘다 오프일수도 둘다 온일수도 하나만 온일수도...있다는 겁니다.
죄수 23명은 오늘 하루만 서로 회의를 할 기회가 있으며
내일부턴 각자 격리 수용될 것입니다.
내일부터 있을 일에 대해 설명 드립니다.
간수가 임의로 한명을 독방에서 꺼내어 그 스위치가 있는 방에 데려갑니다.
그 한명은 두개의 스위치중 "반드시" 한개를 변화시켜야 합니다.
반드시 ⓐ ⓑ 둘 중 하나를 온 혹은 오프로 바꿔야 합니다.
그리고 어떤 표시도 할수 없습니다. 그가 들어오기 전과 후의 변화는
스위치 하나의 on/off 일 뿐입니다.
이런식으로 하루에 몇번이 되든 한명씩 그 방에 드나듭니다.
한 명만 계속 들여 보낼수도 있습니다.
꼭 23명 모두룰 순서대로 들여보내란 법이 없다는 뜻입니다.
여기서 문제가 문제가 나갑니다.
23명이 전부 한번 이상 들어갔음이 확실하다고 생각되면
누구라도 선언을 할 수 있다고 합니다.
"23명이 전부 들어왔다!!" 라고 선언을 하고나서
그 선언이 진실이면 전부 사면되고
그선언이 거짓이면 즉 한명이라도 그 방에 들어가지 못한사람이
있다면 모두의 사면 기회는 박탈됩니다.
오늘은 하루뿐인 대화의 시간입니다.
23명 모두 머리를 짜내어 사면의 기회를 잡아야 합니다.
어떻게 하면 될까요?
답
일단 쉽게 생각할 수 있는 방법부터.
카운트맨 한 사람을 선정한 다음, 이 사람에게 각자가 그 방에 들렀다는 정보를 전해 주고, 그 정보로부터 모든 사람이 방에 왔음을 알 때 선언을 하게 합니다.
정보를 전하는 방법이 문제인데, 카운트맨이 정보를 받기 전까지는 그 정보가 그대로 보존되어야 하니까, 손대지 말아야 할 스위치가 필요합니다.
따라서, 각 죄수의 스위치 조작 방법은, A 스위치를 켠 적이 없을 때, A 스위치가 꺼져 있으면 켜 두고 만약 A 스위치가 켜져 있으면 손대지 말고 그냥 나가...면 안 되니까 B 스위치의 상태를 바꿉니다. A 스위치를 켠 적이 있는 경우도 B 스위치를 바꿉니다.
결국 B는 일종의 dummy인 거죠.
이제 카운트맨이 이 방에 들어 왔을 때, A 스위치가 꺼져 있으면 아직 아무도 안 들어왔다는 뜻이니까 역시 dummy인 B를 바꾸고 나갑니다. 만약 방에 들어왔을 때 A 스위치가 켜져 있다면, A 스위치를 처음 켠 사람이 왔다갔다는 것이니까, 신호를 받았다는 뜻으로 A 스위치를 끄고 나갑니다. 그러면서 카운트맨은 카운터를 하나 올립니다.
이렇게 해서 카운터가 22가 될 때까지 들락날락하면 됩니다.
한 가지 문제가 있죠.
그 방의 스위치가 처음에 어떻게 되어 있는지에 대한 정보가 없습니다.
만약 처음에 A 스위치가 꺼져 있었다면 이 방법이 잘 작동하지만, A 스위치가 처음부터 켜져 있을 수도 있습니다.
이렇게 되면 카운트맨을 제외한 다른 죄수는 A 스위치에 손을 댈 수가 없으니까, 극단적인 경우 22명이 모두 방에 왔다가 A 스위치는 손도 못 대고 나간 다음에 카운트맨이 들어오고서야 카운터가 1이 될 수도 있습니다.
이 경우 카운트맨에 의해 A 스위치가 꺼진 다음 죄수들이 다시 A 스위치를 켜게 되는데, 21명이 켜는 것으로 카운트맨의 카운터가 22가 되어 버립니다.
따라서, 처음부터 A 스위치가 켜져 있을 가능성에 대한 대비를 해야 합니다.
방법은 간단합니다. 각 죄수가 "두 번씩" A 스위치를 켜면 됩니다.
만약 처음에 A 스위치가 켜져 있는 상태로 출발했다면, 앞서의 극단적인 경우를 생각할 때, 카운트맨의 카운터가 22가 되면 모든 죄수가 그 방에 들어왔다 나갔음을 알 수 있습니다.
만약 처음에 A 스위치가 꺼져 있는 상태로 출발했다면, 각 죄수가 많아야 두 번 A 스위치를 켜게 되니까 최악의 경우 카운터가 44가 되면 모든 죄수가 그 방에 들어왔다 나갔음을 알 수 있습니다.
그러므로 카운트맨의 최선의 전략은 카운터가 44가 될 때 "23명이 전부 들어왔다!!"고 선언하는 것입니다.
