| [ QuizWit ] in KIDS 글 쓴 이(By): Tesak (몽마르뜨) 날 짜 (Date): 1999년 5월 8일 토요일 오전 12시 20분 38초 제 목(Title): [답] 해적과 금덩어리 맞습니다. 유명한 퍼즐입니다. 그리고 제가 퍼온곳은 Scientific American 99년 5월호 Mathematical Recreations 칼럼입니다. 이 칼럼은 재미있는 솔루션을 제공하고 있습니다. 솔루션의 백미는 해적의 수가 200명 이상일 때입니다. 이 퍼즐의 오리지날 버젼은 해적의 수가 10명일 때, 가장 바람직한 분 배 방법이 무엇인지를 묻는 것인데, 답은 많은 분들이 푸신 바와 같습니다. 다시정리해보겠 습니다. 편의상 가장 극악 무도한 해적에게 놓은 번호를 부여하겠습니다. 즉 10명인 경우, 가장 악날한 해적이 10번, 가장 유순한 해적이 1번입니다. 2명일 때, 2:100개, 1:0개 3명일 때, 3:99개, 2:0개, 1:1개 4명일 때, 4:99개, 3:0개, 2:1개, 1:0개 5명일 때, 5:98개, 4:0개, 3:1개, 2:0개, 1:1개 . . . 10명일 때, 10:96개, 이하 홀수번호 해적:0개, 짝수번호 해적:1개씩 해적의 총 수가 200명 이하일 때는 이 방법이 통합니다. 즉 200명일 때, 짝수번호 해적: 1개씩, 홀수번호 해적:0개 그렇다면 해적의 수가 201명 이상일 때는 어떻게 될까요? 201명일 때, 가장 악날한 해적은 살아남을 수 있습니다만 자신은 금덩이 한개도 갖지 못합니다. 즉 1-199사이의 홀수번호 해적들에게 금덩이 하나씩 나누어주고, 자신도 찬성표를 던지면 101개의 찬성표를 확보할 수 있습니다. 202명일 때, 역시 101개의 찬성표를 얻을 수 있습니다. 201번의 제안아래에서 금덩이를 하나도 받지 못하는 해적들, 다시 말해 101명(1-200번 사이의 짝수번호 해적 100명과 201번) 중 100명을 뽑아 금덩어리 하나씩 나누어 주고(나누어 주는 방법의 수는 101가지겠죠), 자신은 하나도 갖지 못한채 찬성표를 던지면 101표를 얻을 수 있습니다. 203명일 때, 불행히 이 해적은 죽음을 면치 못합니다. 아무리해도 102표는 확보 불가능 입니다. 204명일 때, 이제 204번 해적은 203해적의 불행한 조건(204가 어떤 조건을 내걸더라도 203은 승락할 수 밖에 없다는 것)을 잘 알고 있습니다. 202가 제안했을 때 금덩어리를 받지 못하는 사람들 중에서 100명을 뽑아 금덩어리를 하나씩 주어 100표를 확보하고, 203과 204표를 합하면 102표. 과반수가 됩니다. 205, 206, 207명일 때, 과반수 표 획득의 실패로 죽음을 면치 못합니다. 208명일 때, 205, 206, 207의 불행한 조건이 208번의 해적을 살릴 수 있습니다. 204의 제안에서 금덩어리를 받지 못하는 해적 중 100명을 뽑아 금덩어리를 주고 100표 확보하고 205, 206, 207, 208의 4표를 더하면 104표. 과반수가 됩니다. . . . 이렇게 해서 새로운 규칙이 발견됩니다(캘리포니아의 Stephen Omohundro가 발견한 바와 같이). 즉 해적의 수가 202명 이상인 경우는 해적의 수가 '200+2의 거듭제곱'일 때만 제안자가 살아남을 수 있습니다. 예를 들어 해적의 수가 500명일 경우는 가장악날 한 해적부터 44명이 바다에 빠져 죽음을 당하고 비로소 456(200+2^8)해적에 와서야 그의 제안이 과반수의 찬성표를 얻게됩니다. 그의 제안은 1-199사이의 홀수 번호 해적 100명에게 금덩어리를 하나씩 나누어 주어 100표 확보. 그리고 456에서 329사이의 해적 128명이 무조건 찬성표를 던지게 되므로 총 228를 건질 수 있습니다......... |