캐리비안의 잔혹한 해적 5명이 금화 100개를 손에 넣었다. 각 해적은 1번부터 5번까지 번호를 가졌고, 1번 해적부터 번호 순서대로 금화를 어떻게 나눌지 방법을 제시한다. 각 해적이 방법을 제시할 때마다 찬반 투표를 해서 과반수(50% 초과)의 찬성을 얻으면 그 방법대로 금화를 나눈다. 만약 그렇지 못하면 그 방법을 제시한 1번 해적을 물에 빠뜨리고 다음 해적이 방법을 제시한다. 단, 찬반 투표에 본인도 참여하며 해적들은 아래와 같은 규칙을 지킨다.
①다섯 명의 해적 모두 전략을 따질 수 있을만큼 충분히 똑똑하다.
②각 해적은 자신의 생존을 최우선으로 하며 생존이 보장되는 한 최대한 금화를 많이 가지려 한다.
③각 해적은 자신의 찬반에 따라 생존 여부 및 얻는 금화 수의 변화가 없으면, 반대표를 던지는 심보가 있다.
④나누는 방법을 제시하는 해적은 생존 여부 및 얻는 금화 수의 변화가 없으면, 앞번호일수록 금화를 더 주는 방법을 제시한다.
문제1
1번 해적이 물에 빠지지 않으려면 어떤 방법을 제시해야 할까?
문제2
문제1을 바탕으로 해적이 n명 있고 금화는 G개 있다고 하자. 이 때, p% 초과의 찬성을 얻어야 받아들여진다는 규칙이 있다면, 일반적으로 어떤 방법을 제시할 수 있을까? 단, 금화의 개수 G는 해적의 수 n보다 매우 크다. (G
n)
-
문제 1의 경우 4, 5번 해적만 남았을때 부터 생각하면 쉽습니다.
4번이 5번에게 금화를 다 준다고 해도,
5번은 4번이 물에 빠져 죽이는 것을 바랄 것입니다.
즉 4번입장에서는 이 전까지 분배가 끝나야 하며, 5번은 여기 까지 끌고 와야하므로 일반적으로 반대표를 던질 것입니다.
3,4,5번만 남았다고 가정해봅시다.
4번은 더 이상 피할곳이 없기때문에, 울며 겨자먹기로 무조건 찬성표를 던져야합니다.
그렇게되면 3번은 어떻게 제시하든 금화와 목숨을 둘다 챙길 수 있습니다.
즉, 3번 역시 자기 차례가 될때까지 기다리는것이 유리합니다.
2,3,4,5번만 남았다고 가정해봅시다.
3번에게 가게되면 끝나는 것을 알게되는 5번의 찬성 표를 이끌기 위해서는 2번은 적어도 1개의 금화를 5번에게 주어야합니다.
또한 4번은 3번까지 가게되면 불리함을 알기에,
2번은 4번에게 금화 하나를 줌으로서 찬성 표를 얻을 수 있습니다.
즉, 98:0:1:1 로 하는 것이 2번에게 유리합니다.
이제 처음으로 돌아가봅시다.
3번은 2번이 본인에게 금화를 하나도 주지않을 것을 알고있기때문에,
금화 한 개라도 받으면 찬성 표를 던질것입니다.
반대로 2번은 이번만 넘어가면 자신은 금화 98개를 챙길 수 있기때문에,
무조건 반대 표를 던질것이므로 그냥 0개 주는것이 1번에게 이득입니다.
4번은 2번까지 가게되면 1개는 확정이므로,
2개이상 받지못하면 반대 표를 던질것입니다.
그러면 1번은4번에게 2개를 주어야 합니다.
자, 과반수가 넘었네요.
1번은 97:0:1:2:0 으로 주어야 최대한의 이득을 볼수있습니다.
-
문제2의경우 p값이 매우 중요합니다.
문제 1처럼 접근하겠습니다.
마지막 2멍이 남았을 경우 p값이 50%가 넘는다면 n번이 유리하지만,
그것이 아니라면 n-1번이 유리합니다.
마지막 3명이 남았을 경우 p값이 50%이상과 관계없이 누군가는 금화한개에 찬성표를 던집니다.
즉 p값이 66%이하이면 n-2번이 유리합니다.
p값이 그 이상이면 n-2번역시 n번과같은 처지가됩니다.
마지막 4명이 남았다고 해봅시다.
p값이 67%이상이라면 금화한개씩 n번과 n-2번에게 주면 되고,
그이하라해도 n-1번에게 금화한개를 주면 찬성표를 받게되어 생존할수있습니다.
만약에 p값이 75%이상이면 어떻게될까요?
n-3번은 어떻게 할 도리가 없이 죽게됩니다.
즉, n-a번은(단 a<n) p값이 a/a+1이면 죽게되어 금화 한개만 주더라도 찬성 표를 던져야합니다.
또한 문제 1의 4번과 같이, 이런 상황을 겪는 자가 앞에 b명 더 있다면 b+1개를 받아야 찬성표를 던집니다.
p값이 50%이상인 경우 보겠습니다.
p=a/a+1이라 하겠습니다. 그리고 n-a-1번이 남았을 때 부터 올라가보겠습니다.
n-1번을 제외하고 나머지 사람은 금화 한개만 주면 찬성표를 던지게 됩니다.
본인의 찬성표까지 합해서 n-a-1번은 생존할수 있게 됩니다.
그렇다면 분배는 G-a+1개를 본인이 가지고 나머지를 n-1번을 제외한 사람들에게 하나씩 주면 되겠네요.
n-a-1번위도 별반 다르지 않습니다.
n-a-1번은 무조건 반대표를 던질것이고, 그렇기 때문에 n-a-2번은 나머지 표를 모두 찬성을 받아야합니다.
n-1번은 본인이 아무것도 받지못함을 알기에,
하나만 주어도 되고, 나머지는 2개를 주면 됩니다.
이것을 식으로 바꾸어 보겠습니다.
1번은 p값이 a/a+1번일때
G-a(n-a-1)+1+(n-a-2)/2-k 개를 1번이 가질수있습니다.
*k=(n-1)/(a+1)-1 로 소수점부분을 제외합니다. (n-a-2)/2부분도 마찬가지로 소수점은 제외합니다.*
-
50%미만은 시간상 나중에 하겠습니다.
이런 식을 써보는 것이 처음이라, 실수나 잘못생각한것이 있을 수 있습니다.
좋아요0 -
안녕하세요! 주니어폴리매스 멘토입니다.
주어진 비율 p값이 특정한 상황(p = a / (a+1)) 일때의 경우에 대해서 자세한 풀이를 남겨주셨습니다.
가장 마지막 사람이 무조건 반대 표를 던진다는 아이디어로 잘 풀어주셨습니다.
하지만 50% 이상의 p값은 a / (a + 1) 형태의 값이 아닐 수도 있다는 점을 일단 유의하셔야 합니다! (예를 들어 60%는 3/5이고, 이는 a/(a+1) 꼴로 나타나지 않습니다.)
1번이 받을 수 있는 금화의 수를 G와 n과 p를 이용한 문자로 한 번에 나타내는 것 보다 좀 더 단계적인 방향을 제시해주셔도 좋을 것 같습니다.
단계적인 방향이라는 것은 해적이 n명일 때와 n+1명일 때의 전략 사이의 관계를 밝히는 것을 뜻합니다.
아니면 코딩이 익숙하신 분들이 있다면 어떻게 알고리즘으로 구현할 수 있을 지 생각해보셔도 좋을 것 같습니다!
좋아요0 -
p= a/(a+1) 이 아닌 경우도 있지만, 그사이의 확률 (예를 들어 1/2와 2/3사이의 확률:3/5등)은 별로 중요하지않게 보았습니다.
그 사이값이여 봤자 어차피 영향을 주는 요인은 a/a+1을 넘냐 안 넘냐에 따라 달라지기때문입니다.
답변 감사합니다. 지금 보니까 수식이 상당히 복잡하네요.
더 간결하고 명료하게 바꿀려고 노력하도록 하겠습니다.
좋아요1
-
-
자신의 순서 = i
자신이 가질 금화 = g - ((n / 100 * p - 1) + 2 * (i - 1)) * ((n / 100 * p - 1) / 2)
-
-
-
-
일단, 4, 5번만 남았을 때부터 생각해봅시다. 5번 해적이 반대를 하면 4번은 죽을테니 5번은 무조건 반대를 할겁니다.
그리고 5번 해적은 이 상황으로 오는 것이 좋으니 처음부터 반대를 할거고요.
3, 4, 5번이 남은 상황으로 가봅시다.
5번은 무조건 반대니까 4가 살려면 3이 죽지 않아야 하고, 5는 무조건 반대를 할 것이기 때문에 4는 찬성을 할 것입니다.
따라서 3번도 이 상황까지 와야 하니 처음부터 반대를 할 것입니다.
2, 3, 4, 5번이 있는 상황을 봅시다.
3, 5이 반대를 하면 2는 죽기 때문에 2는 3 또는 5번의 찬성을 받아야 합니다.
그러나 3번은 자신이 금화를 모두 가져갈 수 있다는 것을 알기 때문에 5번에게 금화를 1개 이상 주면 됩니다.
또 4번은 2번이 죽으면 금화는 못받지만 살 수는 있기 때문에 2번은 4번에게도 금화를 1개 이상 줘야합니다.
따라서 2번은 98 : 0 : 1 : 1로 배분할 것입니다.
그럼, 맨 처음의 상황을 생각해봅시다.
2번은 자신의 차례가 오면 자신이 유리해지기 때문에 금화 99개 이상 주지 않는 이상 반대일겁니다.
그리고 3번은 차례가 2번에게 넘어가면 금화를 못 받을 것을 알고 있으므로 금화를 1개 이상 받으면 찬성을 할 것입니다.
4번은 2번 차례가 되면 1개를 받을 수 있으므로 2개 이상 줘야합니다.
따라서 97 : 0 : 1 : 2 : 0으로 줘야한다.
2번은 모르겠네요 : (
-
