1. 개요
해적들의 금화 배분량을 추론하는 고전 문제.
2. 문제
| 해적 5명이 금화 1000개가 들어있는 보물상자를 발견했다. 일반적인 상황이었다면 공정하게 200개씩 분배했겠으나 욕심이 많고 서로를 무척이나 싫어했던 해적들은 금화를 둘러싸고 오랜 시간 신경전을 벌였다. 긴장 상태가 해소되지 않자 해적 중 한 명이 다음과 같은 제안을 한다. "이봐, 우리 이러지 말고 이렇게 하자고. 먼저 제비뽑기를 해서 우리들끼리 순서를 정하고, 앞 순서가 나온 사람이 1000개의 금화를 어떻게 배분할지 제안을 하는거지. 만약 제안자를 포함해서 나머지 해적들 중 '과반'이 분배안에 동의한다면 그 제안대로 분배하고, 그렇지 않을 경우 제안자를 죽이고 다음 순서를 가진 사람이 제안자를 하는 거지. 어때, 동의하지?" 나머지 해적들이 이 제안에 동의했고, 바로 제비뽑기를 해서 A-B-C-D-E 순으로 순서를 정했다. 해적들은 서로 뒷거래를 하지 않으며[1], 모두 합리적으로 판단한다고 했을 때 금화는 어떻게 분배될까? 찬성/반대만 존재하며 기권은 없다. 해적들은 무한히 탐욕스럽고, 또한 매우 합리적이며, 서로를 싫어한다. 따라서 이들은 금화를 1개라도 더 얻을 수 있다면 망설임 없이 제안자를 죽이며, 같은 개수일 경우에도 죽이는 것을 선택해 상대의 죽음을 즐길 것이다. 물론 죽이지 않는 것으로 금화를 1개라도 더 얻을 수 있는 경우엔 죽이지 않는다. 그리고 절대 실수나 계산 착오를 하지 않는다. 주의해야 할 것은 "과반의 찬성"이란 표현인데, 절반 이상이 아니라 절반 초과여야 한다. 즉 5명일 때는 자신 포함 3명의 동의가 있어야 하고, 4명일 때 역시 3명의 동의가 있어야 한다. |
3. 해답
- [ 보기 · 닫기 ]
- ||<tablebordercolor=#552582>얼핏 굉장히 추상적이며 답이 없을 것 같은 문제이지만, 해적들이 항상 합리적으로 판단한다는 것을 염두에 두고 역산을 이용하면 생각보다 쉽게 구할 수 있다.
일단 D와 E 두 명일 때는 어떤 식으로 결론이 날 지 먼저 생각하고, 한 명씩 늘려나갔을 때 해적들이 할 합리적인 판단을 고려해서 최종 결과를 구하면 된다.- D, E
E가 제안을 반대한다면 D는 무조건 죽으며 E가 금화 1000개를 독차지하게 된다. 설령 D가 이를 피하기 위해 금화를 모두 E에게 준다는 제안을 하더라도, 찬반과 관계없이 금화를 독차지하는 E는 D를 죽이기 위해 제안에 반대할 것이다.
D가 살 수 있는 방법 없음
- C, D, E
C가 죽고 나면 D와 E는 위의 상황이 된다. 즉 D는 꼼짝없이 죽는다. 이를 알고 있는 E의 입장에선 금화를 독차지하고 C와 D도 죽이기 위해 무조건 C의 제안을 반대할 것이다. 하지만 D는 자신의 목숨을 살리는 것이 1순위이기에 분배와 관계없이 C가 어떤 제안을 해도 찬성할 수밖에 없다. 그러면 찬반이 2대 1이니 결국 C는 어떤 제안을 해도 무조건 금화를 독차지할 수 있다.
C=1000, D=0, E=0
- B, C, D, E
여기서 B가 죽게 되면 C는 앞서 설명한 것처럼 금화를 독차지할 수 있다. 따라서 C는 B가 어떤 제안을 해도 무조건 반대할 것이므로 D와 E 둘 다 B에게 찬성을 해 줘야만 B가 살아남을 수 있다.
D와 E의 입장에서, 만액 B가 금화 0개를 제안한다면 어차피 찬반에 관계없이 금화를 얻지 못하니 B라도 죽이려고 제안을 반대할 것이다. 반대로 B가 D, E에게 금화 1개씩을 주기로 제안한다면 찬성했을 땐 금화 1개를 얻고, 반대한다면 하나도 얻지 못하므로 합리적으로 판단하는 D, E는 B의 제안에 찬성할 것이다.
B=998, C=0, D=1, E=1
- A, B, C, D, E
A가 죽었을 때 예상되는 분배는 위와 같고, A는 넷 중 둘의 동의만 얻는다면 과반이 된다. 해적들은 합리적인 판단을 하기에 A가 죽었을 때 자신이 얻는 금화에서 단 하나만 더 준다고 하더라도 A를 죽이지 않는 선택을 할 것이다.
금화 999개를 줘야 포섭이 가능한 B와는 달리 C는 금화를 1개만 줘도 포섭이 가능하므로 A가 가장 많은 금화를 받기 위해 C에게 금화 1개, D와 E 중 한 명에게 금화 2개를 지급하고 나머지를 A가 가지면 세 명의 찬성을 받을 수 있다.
경우에 따라 분배안이 통과하지 못하면 제안자를 죽이는 것이 아닌 그냥 이후의 분배에서 배제시키는 규칙으로 나오는 판본도 있다. 이 경우에는 해적들이 죽지는 않으므로 분배안이 약간 달라진다. 마찬가지로 거꾸로 구하면 쉽게 구할 수 있으니 직접 구해보자. 또는 과반이 아닌 한 사람의 의견(A의 의견에는 B만, B의 의견에는 C만 이런 식으로)만으로 죽일지 살릴지 결정하기도 한다. 또는 과반수를 초과하지 않고 이상인 경우에도 인정되는 경우도 따져볼 수 있다.
판본에 따라 제안을 하는 쪽이 선장이며 선장이 죽으면 항해사(부선장) - 1등선원 - 2등선원 순서로 선장을 맡는다고 되어 있는 경우도 있다. 물론 이 경우엔 별 차이는 없다. 결과를 보면 이쪽이 조금은 더 그럴듯해 보이는 점은 있다. 선장이 많이 가지고 선원들은 조금만 가지게 되니.
6명의 경우 답은 996:0:1:2:0:1 또는 996:0:1:2:1:0이다. || - D, E
[1] 이 부분이 굉장히 중요하다. 저 조건 하나를 추가하는 순간 문제에 무수히 많은 변수가 존재하기 때문, 예를 들자면 B, D, E가 서로 금화를 나눠가지는 조건으로 A에게 반대표를 날리는 것.