top of page
33.jpg
55.jpg

KAIST부설 한국과학영재학교 온라인 과학매거진 코스모스

  • 블랙 페이스 북 아이콘
  • 블랙 인스 타 그램 아이콘

당신은 감옥에서 탈출할 수 있으시겠습니까?

100인의 죄수 문제를 들어본 적이 있는가? 여러 가지 버전이 있는데, 기사에서 다루어볼 것은 모자 문제와 사물함 문제이다. 먼저 문제를 제시해볼 테니, 어떻게 하면 좋을지 생각해보면 좋을 듯 하다.

※본 기사에 나오는 100인의 죄수 문제는 기존 문제를 약간 재구성한 것입니다.


100인의 죄수

100인의 죄수 문제

100인의 죄수가 교도소에 감금되어 있다. 밖에는 전쟁이 나버린 바람에 인도적 차원에서 교도관들은 죄수들을 죽이거나 탈옥시키기로 마음먹는다. 그러나, 죄수를 무척이나 싫어했던 한 사람은 이들을 절대 감옥에서 빼주지 않기를 원했다. 그냥 죽여버리면 명분이 없기 때문에 죄수들이 이기기 쉽지 않은 두 가지 게임을 제시해, 이 게임을 이기면 살려주고, 지면 죽여버리겠다고 말한다. 다만, 게임은 전날에 미리 알려주며, 죄수들끼리 모여 게임 시작 전까지 전략을 세울 수 있다.


첫 번째 게임은 사물함 번호 맞추기이다. 죄수들은 각각 1번부터 100번까지의 번호를 부여 받고, 교도관은 사물함 방에 있는 100개의 사물함 안에도 1부터 100까지 숫자가 쓰여져 있는 쪽지를 미리 넣어둔다. 죄수들은 처음에 대기실에서 대기하고 있다가 한 명씩 순서대로 사물함 방으로 들어간다. 죄수는 100개의 사물함 중 50개를 열어보며, 그 중 죄수 자신의 번호가 있다면 대기실과 소통이 불가능한 다른 방으로 이동해 게임이 끝날 때까지 대기한다. 다만 이동하기 전에 사물함 방은 처음 들어온 상태로 원상복구 해야하며, 사물함에 어떠한 표시도 남길 수 없다. 부정행위가 적발될 경우 모두가 사형당한다. 만일 죄수 자신의 번호가 없다면, 그 즉시 게임은 종료되며 모든 죄수는 사형을 당한다.


운 좋게 모두가 첫 번째 게임을 통과했다면, 처음보다는 조금 쉬운 두 번째 게임이 기다리고 있다. 두 번째 게임은 모자 색 맞추기이다. 죄수들은 첫 번째 게임에서 부여 받은 번호에 따라, 앞에서부터 일렬로 앉게 된다. 모든 죄수는 앞을 보고 앉아있으며, 교도관이 각각의 죄수의 머리 위에 검은색 혹은 흰색 모자를 랜덤하게 씌워준다. 이때, 교도관은 몇 개의 모자가 흰색이고, 몇 개의 모자가 검은색인지 알려주지 않으며, 모든 죄수는 자신의 앞에 앉은 모든 죄수들의 모자 색을 알아볼 수 있다. 가장 뒤에 있는 죄수부터 자신의 모자 색을 말하며, 이때 자신의 모자색 은 교도관에게만 들리게 말하며, 교도관이 죄수가 무엇을 말했는지는 정면의 화면에 띄워준다. 모자를 떨어뜨리는 등의 꼼수를 사용하면 모두가 사형당한다. 만일 모자 색이 틀렸다면 모두가 즉시 사형되며, 모두가 제대로 말한다면 결국 감옥을 탈출할 수 있다.


당신은 감옥을 탈출할 수 있겠는가.


첫 번째 게임

만일, 랜덤하게 배정된 상자에서 랜덤한 50개의 상자를 고를 경우, 탈옥할 수 있는 확률은 얼마일까? 당연하게도, 그 확률은 매우 낮을 것이다. 실제로 계산해보면, 아래와 같다.



한 명이 50개를 골랐을 때 자신의 숫자가 나올 확률은 0.5(50%)이지만, 100명이 모두 그걸 성공할 확률은 매우 낮아 정말 운이 좋지 않은 이상, 사형을 당할 것이다. 그렇다면 이 확률을 높일 수 있는 방식은 무엇일까? 그 해답은 Peter Bro Milterson의 논문, The cell probe complexity of succinct data structures에 나와있다. 바로 “루프”를 생각하는 것이다.


우선, 죄수가 방에 들어가면, 자신의 번호와 같은 상자를 연다. 이후, 그 상자에 있는 번호의 상자를 열고, 또 그 상자에 있는 번호의 상자를 열고, … 와 같은 방식으로 상자를 연다. 그렇다면 언젠간 자신의 번호가 있는 상자가 나타나게 될 것이며, 그러면 다시 처음 열었던 상자로 가게 되므로, 하나의 루프를 이루게 될 것이다.


출처: Youtube channel, "Veritasium", The Riddle That Seems Impossible Even If You Know The Answer

그렇다면, 루프의 길이가 50 이하이라면, 자신의 번호를 50회의 시행 이내에 찾을 수 있을 것이다. 결국, 모든 죄수가 성공하기 위해서는, 존재하는 모든 루프의 길이가 50 이하이면 된다. 전체에서 루프의 길이가 50보다 큰 것이 있는 경우를 제외하면 되므로, 아래와 같이 확률을 구할 수 있다.



확률이 무작위로 할 때에 비해 엄청나게 증가한 것을 볼 수 있다. 이 정도면 가위바위보 수준의 승률이므로 운에 맡겨도 되지 않을까..?


교도관의 트릭

그렇지만, 이 게임에서 절대로 사물함 안에 쪽지를 랜덤하게 두었다고 하지 않았다. 죄수를 좋아하지 않는 교도관이라면, 게임에서 반드시 이기기 위해서 루프의 길이가 50보다 큰 것이 존재하도록, 혹은 루프의 길이가 100이도록 쪽지를 배치해 두었을 것이다. 그렇다면, 죄수들이 이길 수 있는 방법은 그저 전략 없이 운에 맡기는 0.0000…81%뿐인 것일까? 당연히 그렇지 않다. 바로 “수 더하기”라는 전략을 사용하면 된다. 하나의 자연수 n을 생각하자. 처음에 죄수 자신의 번호에 n을 더한 상자를 열고, 쪽지에 있는 번호에 n을 더한 상자를 열고, … 와 같은 방식으로 진행하면, 루프는 완전히 초기화되어 랜덤해진다. 그렇기에, 이 경우 다시 확률이 약 31%가 된다. 여기서 100 다음의 수는 1, 2, 3, … 와 같이 생각하도록 한다.


두 번째 게임

자, 이제 약 31%의 확률을 뚫었다면 두 번째 게임을 진행할 수 있다. 두 번째 게임의 경우 정말 간단한 전략으로 확률을 높일 수 있다. 만일 전략 없이 운만으로 승부를 보려고 한다면, 한 사람당 맞출 확률은 0.5(50%)이므로, 모두가 죽지 않고 생존할 확률은 아래와 같다.



무작위로 할 경우, 첫 번째 게임에서 무작위로 한 것의 경우와 동일하다. 이번 게임에서 사용할 전략은, 홀짝성이다. 우선, 제일 앞에 있는 사람은 앞 사람들의 흰색 모자가 짝수 개인 경우 흰색 모자라고 답하고, 홀수 개인 경우 검은색 모자라고 답한다. 그렇다면 그 앞의 사람은 자신의 앞에 있는 사람들의 흰색 모자 수가 홀수 개인지 짝수 개인지 알기 때문에, 이 사실을 바탕으로 자신의 앞에 있는 흰색 모자의 개수의 홀짝성이 자신의 바로 뒷 사람이 말한 홀짝성과 다르다면 흰색 모자를(자기 자신이 흰색 모자를 쓰고 있기 때문에 홀짝성이 달라진 것이다!), 같다면 검은색 모자를 선택하면 된다. 즉, 이 전략으로는 첫 사람만 자신의 모자 색을 맞추면 모두가 생존할 수 있게 되는 것이다. 특히 모자는 랜덤하게 씌워지므로 첫 사람이 자신의 색을 맞출 확률은 0.5(50%)라고 말할 수 있을 것이다.


탈출?

결국, 탈출할 수 있는 확률은 첫 번째 게임을 승리할 확률과 두 번째 게임을 승리할 확률을 곱한 것이기 때문에 때문에 아래와 같다.



결국, 이 전략을 따른다면, 당신은 15.6%의 확률로 생존하게 된다! 무조건 탈출이 가능하다고 말할 정도의 수치는 아니지만, 그래도 전략이 없을 때보다는 생존 가능성이 훨씬 높아진 것이니, 의의는 있다. 이제 15.6%의 확률을 뚫을 수 있을지는 운에 기대어보자. 세상에 100%라는 것은 존재하지 않으니까. 만일 이보다 더 높은 확률로 탈출할 수 있는 전략이 있다면, 댓글로 생각을 공유해보면 좋을 것 같다!


 

정지훈 | Mathematics & Computer Sci. | 지식더하기


참고자료

[1] Youtube channel, “Veritasium”

[2] AnnaGála, Peter BroMiltersen, The cell probe complexity of succinct data structures


첨부 이미지 출처

[1] pinterest

[2] Youtube channel, "Veritasium”


ⓒ KAIST부설 한국과학영재학교 온라인 과학매거진 KOSMOS


조회수 130회댓글 0개

최근 게시물

전체 보기