공평하다는 것은 자기가 받은 케이크 조각보다 더 좋은 조각을 받은 아이가 없을 때를 말합니다. 여기서 더 좋다는 것은 자기 생각에 더 좋은 것으로, 매우 주관적이지요. 예를 들어 1만 원짜리 케이크의 한 조각을 보고 어떤 아이는 가치가 100원이라고 말하고, 다른 아이는 2000원이라고 말할 수 있습니다. 이런 상황에서 모두가 만족하도록 케이크를 나눠 먹으려면 각자 입장에서 자기가 받은 케이크의 값어치가 다른 아이가 받은 것 이상이어야 합니다. 이를 게임이론에서는 ‘envy-free하다’, 즉 ‘질투심이 생기지 않게 할 수 있다’라고 말합니다. 여기서는 그냥 ‘공평하게 나누기’라고 쓰겠습니다.
두셋이서 행복하게 케이크 나눠 먹는 방법은?
두 명이서 케이크를 공평하게 나누는 건 쉽습니다. 한 명이 케이크를 둘로 나누면 다른 한 명이 그 중에 마음에 드는 한 조각을 가져가면 됩니다. 만약 백설공주가 케이크를 자르게 된다면, 아마 최선을 다해 두 조각의 가치가 같도록 만들 겁니다. 그렇지 않으면 심술이가 더 좋은 조각을 가져갈 게 당연하니까요. 심술이는 자기가 케이크를 자르진 않았지만 선택을 먼저 할 수 있으니 불만이 없겠죠.
그렇다면 백설공주와 심술이, 행복이 이렇게 셋이서 케이크를 공평하게 나눠 먹으려면 어떻게 해야 할까요? 둘일 때처럼 백설공주가 케이크를 세조각으로 나눠 놓고, 심술이나 행복이 둘 중 한 명이 먼저 고르게 하는 단순한 방법은 통하지 않습니다. 만약 백설공주가 세 조각으로 케이크를 자른 심술이가 먼저 조각을 고른다면, 행복이가 불만스러울 수 있기 때문입니다.
셋이서 케이크를 나눠 먹는 방법은 1960년대 미국의 수학자 존 셀프리지와 영국의 수학자 존 콘웨이가 비슷한 시기에 독자적으로 발견한 방법이 있습니다. 흔히 ‘셀프리지-콘웨이 방법’이라고 부르는데, 케이크를 최대 6조각으로 나누고 칼질은 최대 5번 하게 됩니다(아래 그림 참고).
이렇게 케이크를 나눠 먹으면 모든 사람이 남이 가져간 것보다 자기 조각이 나쁘지 않다고 여긴다는 사실을 수학적으로 증명할 수 있습니다. 그런데 사람 수가 2명에서 3명으로 한 명 늘어났을 뿐인데 분배하는 방법이 훨씬 복잡해졌습니다. 그러면 4명이라면, 혹은 그 이상이라면 어떻게 케이크를 나눠먹어야 할까요? 한동안 이 문제는 미해결 난제였습니다.
그러던 1995년 미국의 두 수학자 스티븐 브람스와 알란 테일러 교수가 해법을 제시했습니다. ‘브람스-테일러 방법’이라고 불리는 케이크 분배법은 1999년 11월 미국 특허로 정식 등록되기도 했습니다. 하지만 브람스-테일러 방법에는 큰 문제가 있습니다. 케이크를 나눠먹는 사람이 4명만 되도 언제 끝날지, 칼질 횟수가 몇 번 이하인지 알 수 없기 때문입니다. 심지어 이 방법을 쓰면 어떤 큰 수보다 더 많이 칼질하는 방법도 있다는 게 증명돼 있습니다. 예를 들어 4명이서 케이크를 나눠 먹는다고 하면 1억 번 또는 원하는 어떤 수보다 더 많이 칼질하는 경우가 있다는 거지요. 안타깝게도 이후 20년 동안 이 문제를 해결하는 새로운 방법이 나오지 않았습니다.
4명이 공평하게 먹으려면 203번 잘라야
최근 이 문제를 해결하는 획기적인 연구 결과가 나왔습니다. 지난 4월 호주 연방과학산업연구소와 뉴사우스웨일즈대에서 근무하는 수학자 하리스 아지즈와 박사과정 학생인 사이먼 맥켄지가 아카이브(새로운 연구 결과를 공개하는 인터넷 사이트)에 새로운 케이크 분배 방법을 담은 논문을 올린 겁니다.
지난해 두 수학자는 사람 수가 4명일 때 최대 203번 칼질하는 방법을 제시한 논문을 발표했습니다. 이어서 올해 사람 수가 n명으로 늘어나도 공평하게 나눌 수 있는 방법을 제시한 겁니다.
물론 이 방법이 실제 상황에 도움이 되지는 않을겁니다. 방법 자체도 복잡하거니와 사람 수가 5명만 되도 칼질해야 하는 수가 우주의 원자 수보다도 많아져 케이크 부스러기가 원자 하나보다 작아질 수 있겠지요. 하지만 첫 술에 배부를 수는 없습니다. 앞으로 이 방법을 토대로 공평하게 나누는 방법에 관한 연구에 큰 진전이 있지 않을까요?
