케이크 사이 좋게 나누기

간단해 보이지만 간단치 않은 수학문제 하나 풀어 봅시다. 케이크가 보이시나요. 이 케이크을 모두가 만족하도록 나누어 가지려면 어찌해야 될까요? 크기만 똑같이 나누면 누군가 다른 이가 가진 것을 부러워하게 됩니다.

 

생크림 있는 쪽을 모두가 좋아한다면 크기를 조금 작게 나누어야겠지요. 서로 크기가 같은 똑같은 나눔과 크기는 달라도 모두 맘에 들어하는 것은 부러움 없는 나눔이라 부릅시다.

둘이라면 간단하죠.

1. A가 나름대로 둘로 자릅니다.

2. B가 먼저 둘 가운데 하나를 가집니다.

이렇게 나누면 둘 모두 다른 조각을 부러워하지 않을 테니 부러움 없는 나눔이 됩니다.

이제 셋이라면 어떻게 나누어야 할까요?

1. 먼저 $A$가 케이크을 셋($X,Y,Z$)으로 자릅니다. 이제 $B$와 $C$가 각각 가지고 싶은 조각을 하나 이상 고릅니다. 만일 두 사람이 다른 걸 골랐다면 모두 고른대로 가지고 남은 것은 $A$가 가지면 됩니다.

2. $B$와 $C$가 같은 $Y,Z$을 골랐다면 두 사람 생각에는 $X$는 `\displaystyle{\frac{1}{3}}`이 안된다고 생각한 것이지만 $A$는 이를 가져도 맘 상하지 않습니다. 자신이 자른 것이므로.

3. 이제 $Y,Z$를 합친다. 그러면 두 사람에게는 이 새로운 조각이 적어도 전체의 `\displaystyle{\frac{2}{3}}` 는 넘는 것으로 생각될 것입니다. 이제는 합한 것을 둘이서 나누는 방법대로 나누어 가집니다. 이렇게 나누는 것은 똑같이 나눔은 되지만 부러움 없는 나눔은 아니죠.

$A$가 $B$와 $C$가 가진 조각 가운데 하나를 부러워할 수는 있으니까요. $B,C$ 눈엔 같아 보여도 어느 하나가 $A$ 눈에 커 보일 수 있으니까? (세 사람을 위한 스타인하우스의 똑같이 나누기)

다음과 같이 나누면 부러움 없는 나눔이 됩니다.

1. $A$가 주어진 케이크을 셋으로 나누어 $B$에게 줍니다.

2. $B$는 $A$가 나눈 것을 만족한다면 그대로 $C$에게 줍니다. 그렇지 않다면 $B$는 세 조각 중에서 많다고 생각되는 한 조각에서 덜어내어 적어도 가장 큰 것이 두 개 있도록 만들어 $C$에게 줍니다.

3.$C$는 이 세 조각 중에서 가장 크다고 생각되는 조각 혹은 가장 큰 것과 같다고 생각되는 조각을 고르고 나머지를 $B$에게 줍니다. 이제 $B$는 가장 크다고 생각되는 것을 가지면 됩니다. $2$에서 가장 큰 것이 두개 있도록 만들었기 때문에 언제나 고를 수 있죠. 만일 $B$가 덜어낸 조각이 있고 이 조각을 $C$가 선택하지 않았다면 $B$는 이 조각을 가져야만 합니다.

4. $A$는 남은 조각을 가집니다.

어때요 그리 쉽지 않지요. 이를 일반화하면 `n`명이 케이크를 모두가 맘에 들도록 잘 나눌 수 있습니다. 잘 생각해 두셨다가 생일날 케이크 자를 때 아이들에게 문제로 내보세요. 별로 좋은 소리는 듣지 못할 수도 있습니다.

한가지 분명한 것은 한 사람이 자르고 나누어 주기까지 한다면 아무리 좋은 맘으로 똑같이 나누었다고 하더라도누군가는 다른 이가 가진 것을 부러워하게 된다는 것입니다. 따라서 자르는 이는 고르는 것을 나중에 해야 모두가 맘에 들게 나누어 가질 수 있다는 것입니다.