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