퀴즈6 해적들의 금화 문제

해적이 5명 있음
이 멋쟁이들이 금화 1000냥을 손에 넣었음
금화 1000개를 이제
5명이 나눠가질건데
다음과 같은 규칙을 정했음
1) 해적 5명은 각자 서열이 있다. 해적1 부터 해적5까지. 해적1<해적2<해적3<해적4<해적5 순으로 서열이 높다
2) 서열이 가장 높은 사람이 금화 분배안을 제안한다.
3) 제안자를 포함하여 그 분배안에 대한 찬반 투표를 한다. 50% 이상이 찬성하면 그 분배안은 통과되고 금화는 그 안대로 분배된다.
4) 만약에 50% 이상이 찬성하지 않는다면, 제안자는 그자리에서 죽는다
5) 남은 사람들중 서열이 가장 높은 사람이 다시 분배안을 제안한다.
6) 50% 이상이 찬성하여 분배안이 통과될때까지 이 과정을 반복한다.
7) 해적 5명은 모두 매우 똑똑하고, 자신의 이익을 최우선으로 하지만 금화보다는 목숨이 소중하다.
8) 당신은 해적5다
9) 최적의 분배안을 제안해보라.

p.s> 
-금화는 쪼개지지도, 나누어 지지도 않습니다. 자연수라고 생각하면 될 듯.
-자신은 제안자 이므로 당연히 찬성표 입니다. 즉 해적은 총 5명이니까, 2명이 반대하였다면 찬성은 3명인 것입니다.
-최적해 라는 것은, 목숨은 살면서 금화도 많이 갖는 방법입니다. 즉 해적5가 금화를 0냥 갖고 목숨을 건지는 방법이 있고 금화를 10냥 갖고 목숨을 건지는 방법이 있다면, 후자가 전자보다는 적합할 것 입니다.
-만약 금화를 받는 양이 동일하다면, 해적들은 서로를 최대한 많이 죽이려 할 것이다.



답은 아래로 내리면 있어요.
















답)
차례차례 생각해보자.

해적이 2명이 남아있다. 해적1과 해적2.
이 경우 해적2는 무조건 자신이 1000냥을 다 가질것이다. 왜냐면 해적1이 반대해도 자신이 찬성하니까.

해적이 3명이 있다고 해보자. 해적1, 해적2, 해적3.
해적3이 만약 천냥을 다 갖는다면? 해적2는 당연히 반대할 것이다. 해적3을 죽이면 두명만 남게 되니깐 자신이 천냥을 다 가질 수 있을테니깐. 해적1은? 알 수 없다. 찬성하건 반대하건 자신은 갖는 것이 없다. 그러므로 이건 답이 될 수 없다. 그렇다면 해적 2에게 500냥을 주는건 어떠한가? 그러면 해적2는 한푼도 못받느니 찬성할려나? 이 경우도 알 수 없다. 결국 아무것도 받지 못하는 해적1이 찬성할지 반대할지 알 수 없다. 그렇다면? 해적이 3명일때 최적은, 해적1에게 1냥을 주고 해적3이 999냥을 갖는 것이다.
어짜피 해적3을 죽여봤자 해적1은 한푼도 갖지 못한다. 그런 해적1에게 1냥을 준다면 해적1은 당연히 찬성할 것이다. 그러므로 해적이 3명일때의 답은 해적1에게 1냥 해적3은 999냥이다.

이제 해적이 4명 일 때는?
해적 3은 해적 4를 죽일 경우 무조건 999냥을 받을 수 있다. 그러므로 자신이 999냥보다 적게 받는 다면 해적4에게 찬성 할 이유가 없다. 해적2는 해적4가 죽어서 결정권이 해적3에게 갈 경우 한푼도 받을 수 없다. 그러므로 어떻게 해서든지 해적3에게 결정권이 넘어가게 하지 않을 것이다. 하지만 해적4가 자신이 1000냥을 모두 갖고 해적3에게 한푼도 주지 않는다면, 해적3이 찬성할 이유가 없다. 마지막 조건인 '만약 금화를 받는 양이 동일하다면, 해적들은 서로를 최대한 많이 죽이려 할 것이다.' 때문이다. 차라리 해적4를 죽이려 할 것이다. 그러므로 해적2가 한푼이라도 받기 위해선 해적4를 살리고 1냥이라도 받는게 이익이다. 해적4는 자신이 999냥을 갖고 해적2에게 1냥을 주면 된다.

이제 해적이 5명일 땐?
마찬가지로, 해적4는 해적5를 어떻게든지 죽이면 자신이 999냥을 가질 수 있기 때문에 999냥보다 적게 가질 경우 의견에 반대할 것이다. 해적 3은? 해적이 4명일 때의 예를 보면 알 듯이, 해적4가 제안권을 갖게 된다면 자신은 한푼도 받지 못한다는 것을 알고 있다. 따라서 자신이 한푼이라도 받기 위해선 해적5가 이기는게 차라리 낫다. 해적 1역시 마찬가지다. 해적5가 죽어버려서 해적4가 제안권을 갖게 되면 자신은 한푼도 갖지 못한다. 따라서 해적5가 제안할 제안은, 해적1과 해적3에게 1냥씩 주고 998냥은 자신이 갖는 것이다. 매우 똑똑한 해적1과 3은 해적5의 제안에 찬성 할 것이다. 멍청하게 이것에 반대했다가는 자신들은 한푼도 갖지 못할테니깐.

위 식의 일반해는, 해적이 N명일 때 N이 짝수면 짝수번째 해적에게 금화 1냥씩 주고 나머지는 자신이 갖고, N이 홀수면 홀수번째 해적에게 금화 1냥씩 주고 나머지는 자신이 갖는 것이다.

그럼 이만~