조합이론에는 아주 간단한듯 보이지만 풀려면 어렵고 막상 답을 보면 허무한 그런 문제들이 많죠.. 그래서 그냥 심심할때마다 그런 문제들을 하나둘씩 공유해볼까 합니다. 오늘의 문제는 죄수 문제! 참고로 이 문제들은 조합이론에선 유명하다면 유명한 문제들로 그냥 구글 이런데서도 찾아보실수 있을겁니다. <div><br></div> <div>*혹시 더 생각하고 싶으신분들을 위해서 답안은 검은색 칠을 해놓을 테니 클릭+스크롤해서 읽으세요.<br><div><br></div> <div><br></div> <div><b><font color="#ff0000">문제:</font></b> 어느 나라에 사형선고를 받은 죄수가 100명이 있다. 간수가 어느날 이 100명에게 1~100사이의 숫자중 하나가 적힌 종이를 나눠준다. (참고로 각 죄수가 받는 숫자는 반복되지 않음. 즉, 100명의 죄수는 전부 서로 다른 숫자가 적힌 종이를 받는다.) 그 뒤에 간수는 100개의 서랍에 무작위로 1~100까지의 번호가 적힌 종이를 하나씩 넣는다. (물론 마찬가지로 100개의 서랍에는 전부 다른 숫자가 적힌 종이가 들어간다.) 그리고 간수는 다음과 같이 제안한다.</div> <div><br></div> <div>1번 죄수를 시작으로 각 죄수는 총 50개의 서랍을 열어볼수 있다. 만약 1번 죄수가 50개의 서랍을 모두 열기전에 자신의 번호가 적힌 종이가 든 서랍을 연다면 이제 2번 죄수가 들어가 똑같은 방식으로 서랍을 연다. 이렇게해서 만약 100명의 죄수가 모두 종이를 찾아낸다면 100명의 죄수는 모두 사형을 면하지만 한명이라도 실패한다면 모두 사형을 당한다. </div> <div><br></div> <div>그 외 자잘한 사항들: </div> <div><br></div> <div>1. <span style="font-size:9pt;line-height:1.5;">서랍을 열어본 죄수는 다른 방에 따로 격리되므로 죄수들은 정보를 공유할수 없다.</span></div> <div><span style="font-size:9pt;line-height:1.5;">2. 죄수가 서랍을 열어본 뒤에 간수는 종이를 섞지 <b>않은 채로</b> 그냥 서랍문만 닫는다.</span></div> <div><span style="font-size:9pt;line-height:1.5;"><br></span></div> <div><span style="font-size:9pt;line-height:1.5;"><br></span></div> <div>자, 어떻게 하면 죄수들은 가장 높은 확률로 사형을 면할수 있을까? 가장 간단한 대답을 먼저 찾아보자:</div> <div><br></div> <div><br></div> <div><b><font color="#ff0000">답1.</font></b> 모든 죄수가 무작정 아무 서랍 50개를 연다. 그렇다면 각 죄수가 자신의 번호를 찾을 확률은 당연히 1/2이므로 100명의 죄수가 모두 통과할 경우의 수는 고작 (1/2)^100 뿐이 되지 않는다. </div></div> <div><br></div> <div>하지만 이 확률은 조합이론을 이용해 상당히 올릴수 있습니다.</div> <div><br></div> <div><b><font color="#ff0000">답2.</font></b> <span style="background-color:#000000;">이론은 일단 제쳐두고 어떤 방식을 이용해야 하는지 알아보자. 1번 죄수는 들어가서 1번 서랍을 열어본다. 그리고 1번 서랍에서 1이 아닌 다른 숫자가 나온다면 그 숫자의 서랍을 연다. 그리고 이 서랍에 1이 아닌 다른 숫자가 있다면 다시 그 숫자가 적힌 서랍을 연다. 이미 그 서랍의 번호는 이전 서랍에서 나왔으므로 서랍의 번호와 종이의 번호가 똑같을 수는 없다. 이런 식으로 반복한다면 100명의 죄수가 모두 50번안에 자신의 숫자를 찾을 확률은 무려 30%가 넘어간다.</span></div> <div><span style="background-color:#000000;"><br></span></div> <div><span style="background-color:#000000;">왜일까? 개념 자체는 간단하다. 만약 내가 n개의 숫자를 가지고 cycle을 생성한다 생각해보자. 이때 cycle의 길이에 제한이 없다고(물론 n개의 숫자만 있으므로 n을 넘어갈순 없다.) 가정하고 임의로 cycle들을 생성해냈을때 이 중 하나의 cycle이 길이 m을 가질 기대치는 1/m이다. 이 사실을 증명해내는 것 자체는 조합이론의 기본적 상식만 있다면 가능하지만 그 기본적 상식들을 증명하거나 이해하는것은 조금 어려운 편이라고 생각한다. 여하튼 이 기대치를 가지고 만약 임의로 cycle들을 생성했을때 최소 하나의 cycle의 길이가 n/2를 넘어갈 확률을 구하면 약 69%로 수렴된다. 즉 약 31%의 확률로 임의로 생성된 cycle들의 길이는 모두 n/2 이하가 되므로 위에 방식대로 서랍을 열어본다면 모든 죄수가 자신의 번호를 찾을 확률은 30%가 넘어간다.</span></div> <div><span style="background-color:#000000;"><br></span></div> <div><span style="background-color:#000000;">*죄수가 서랍을 연뒤에 간수는 종이를 다시 섞지 않으므로 cycle들은 처음에 한번 생성된 것이나 마찬가지이다.</span></div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.