d라이브러리

수학자들은 피자만 공평하게 나눠 먹지 않았다. 이번엔 케이크다! 처음부터 케이크가 대상이었던 것은 아니다. 놀랍게도 돈과 영토를 나눌 고민을 하다 툭 튀어나온 문제다. 

제2차 세계대전이 끝나고 미국, 러시아 등의 강국이 모여 돈과 영토를 어떻게 공정하게 나눌지 논쟁을 벌였다. 이때 수학자들이 ‘공정한 분배’에 대해 본격적으로 연구하기 시작했다. 폴란드 수학자인 후고 슈타인하우스는 ‘각자가 자신이 생각하는 기준으로 판단한 가치의  1/n이상에 해당하는 몫을 차지하면 공정한 분배가 이뤄진 것’이라고 공정한 분배의 수학적 정의를 내렸다. 1948년 그는 경제학 학술지인 <;이코노메트리카>;에 발표한 ‘공정한 분배 문제’에서 케이크를 예로 들어 토지나 방송 시간 등을 어떻게 공정하게 나눠야 할지 언급했고, 이 문제는 수학과 컴퓨터과학, 정치학에 영향을 미쳤다.

실제로 칼을 들고 케이크를 자르면 아무리 정교하게 하려고 해도 ‘완벽하게’ 같을 수 없다. 미세한 차이라도 반드시 어느 쪽은 크고 어느 쪽은 작다. 이럴 때 서로 불만이 없도록 케이크를 분배하는 것이 ‘공정하게 케이크 자르기’ 문제다.

우선 2명이 나누는 상황으로 생각하면 답은 간단하다. 한 명이 케이크를 반으로 자르고 다른 한쪽이 먼저 고르는 것이다. 자른 사람은 나머지 한 사람이 더 큰 조각을 가져가리란 걸 알고 있으니 최대한 똑같이 자르려고 애쓸 거고, 자기가 자르지 못한 사람은 어쨌든 스스로 생각하기에 더 큰 조각을 가져갈 수 있으니 불만이 없다. 문제는 사람의 수가 늘어날 때다. 슈타인하우스가 제시한 3명이 공평하게 나누는 방법은 아래쪽 표와 같은 ‘고독한 분할법’이다. 

그러나 이 방법이 유일한 답은 아니다. 1960년대 미국 수학자 존 셀프리지와 영국 수학자 존 콘웨이가 비슷한 시기에 각자 발견한 ‘셀프리지-콘웨이 방법’, 1944년 폴란드 수학자 스테판 바나흐와 브로니스와프 크나스테르가 개발한 ‘마지막 감축법’도 있다. 1961년 미국 수학자 레스터 더빈스와 에드윈 스패니어는 손에 땀을 쥘 만큼 역동적인 ‘움직이는 칼 분배법’을 개발했다.  

한쪽 끝에서 반대쪽 끝까지 칼이 움직일 때, 원하는 지점에서 참여자가 ‘멈춰라!’하고 외친다. 먼저 외친 사람에게 조각을 준다. 케이크 분배가 끝날 때까지 남은 사람들은 ‘멈춰라’를 외치고 모든 사람이 케이크를 가지면 분배가 끝나는 방법이다. 동시에 외쳤을 때는 무작위로 사람을 선택한다.  

2016년 호주 수학자 하리스 아지즈와 사이먼 멕켄지는 사람 수가 n명일 때 n^{n^n^n^n^n}번 칼질하면 케이크를 공정하게 나눌 수 있다고 밝혔다. 하지만 이렇게 자르면 누가 케이크를 입에 대보기도 전에 케이크가 썩을 테니 그냥 좀 불공정해도 적당하게 잘라 먹는 것이 좋다.