수학 퀴즈나 퍼즐 문제들을 풀다보면 분배 문제가 자주 등장한다. 공평한 분배? 참가자 모두가 만족스러운 분배를 하려고 하면 어떻게 해야 할까?
일반적으로 두 사람의 분배문제가 가장 많이 등장하는데, 일단 두 사람의 분배 문제를 먼저 다루어 보자.
가장 대표적으로 두 사람의 케익 분배 문제가 있다.
케익이 균등하게 생긴 것이 아니라면, [예를 들어 초코 케익의 경우 초콜렛의 영역이 다르거나, 과일 케익의 경우 과일의 위치 등등] 정확히 절반으로 자르기 힘든 경우가 대부분이다.
이 때 한 사람이 케익을 자르고 나머지 한 사람이 케익을 고르는 방식으로 두 사람 모두 만족스러운 분배를 할 수 있다.
이는 많은 퍼즐, 논리, 심지어 tv의 프로그램 문제에서도 등장하는 그런 류의 게임(?) 이다.
두 사람의 경우는 어느정도 손쉽게 해결되는데, 3 사람 혹은 그보다 더 많은 사람의 경우는 어떻게 하면 참가자 모두를 만족시키게끔 분배가 가능할까?
일단 세 사람의 경우를 생각해보자.
먼저 한 사람이 칼을 잡고 케익을 자르게 하자. 이 때 자르는 케익의 부피가 점점 증가하게끔 자르게 하자. 나머지 두 사람 중 케익의 부피가 1/3 에 적정하다고 생각하는 사람은 그만을 외치고 거기에 해당되는 케익의 양을 가져간다. 그리고 남은 것을 가지고 두 사람의 경우를 반복한다.
이 방식은 쉽게 n 사람으로 확장가능하다. 1명이 칼을 잡고, 칼을 움직여 1/n 에 위치할 때 다른 그만을 외친 사람이 가져가게 하고, 또 그 사람이 빠지는 방식으로 이를 반복하면 다음 round에는 (n-1) 사람이 되고 이를 반복해서 결국 3 사람의 경우, 2사람의 경우로 회기하게 되어 n 사람 모두 만족스럽게 케익을 분배받을 수 있다.
모든 참가자가 이성적이라면 이 방법이 매우 효과적이겠지만, 이 문제는 참가자 중에 탐욕스러운 자가 한명 이상 있다면.... ㅠㅠ
ㅋㅋㅋㅋㅋㅋ