d라이브러리

생일 축하합니다~. 생일 축하합니다~. 사랑하는 수학동아~, 생일 축하합니다! 
여러분 수학동아의 열 번째 생일이에요. 이번 요리는 도저히 케이크를 만들지 않고는 넘어갈 수 없네요. 오븐은 없지만 ‘안 되면 되게 하라’ 정신으로 만들어보겠습니다!

케이크는 하나, 수학동아 편집팀은 여덟 명. 모두 공평하게 나눠 먹으려면 케이크를 어떻게 자르면 될까요? 흔히 생각하는 모양은 원의 중심을 가로지르는 4번의 칼질로 같은 모양의 8개 부채꼴을 만드는 방법일 겁니다. 흠, 확실히 이 방법이라면 아무도 불만이 없겠군요. 

하지만 명색이 수학동아인데 이렇게 특별한 날 평범하게 케이크를 자를 수야 없죠! 케이크 자르기는 수십 개의 논문이 있을 만큼 여러 수학자가 고민한 문제거든요. 도대체 왜 수학자들이 케이크 자르기 문제에 매달렸냐고요? 

제2차 세계대전이 끝나고 미국, 러시아 등의 강국이 모여 돈과 영토를 어떻게 공평하게 나눌지에 대해 논쟁을 벌였습니다. 이때 수학자들이 ‘공평한 분배’에 대해 본격적으로 연구하기 시작했습니다. 폴란드 수학자인 휴고 슈타인하우스는 ‘각자가 자신이 생각하는 기준으로 판단한 가치의  1/n이상에 해당하는 몫을 차지하면 공평한 분배가 이뤄진 것’이라고 공평한 분배의 수학적 정의를 내렸죠. 

이후 슈타인하우스는 1948년 경제학 학술지인 ‘이코노메트리카’에 발표한 ‘공평한 분배 문제’에서 케이크 공평하게 나누기를 언급했고 이 문제는 수학과 컴퓨터과학, 정치학에 영향을 미치게 됐죠. 어떤 방법들이 있는지 궁금하다고요? 그럼 케이크 자르기, 케이크 공평하게 나누기와 관련된 몇 가지 재미있는 방법을 소개해 드리겠습니다. 

질투 없이 케이크 자르기

첫 번째는 게임이론을 사용해 케이크를 자르고 분배하는 방법입니다. 여기서는 기하학적으로 정확히 같은 면적이나 부피를 따지지 않습니다. 게임이론에서 ‘공평한 분배’란 ‘서로 불만이 생기지 않도록 나누는 것’을 의미하죠. 

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

우선 2명이 나누는 상황으로 생각하면 답은 간단합니다. 한 명이 케이크를 반으로 자르고 다른 한쪽이 먼저 고르는 거예요. 자른 사람은 나머지 한 사람이 더 큰 조각을 가져가리란 걸 알고 있으니 최대한 똑같이 자르려고 애쓸 거고, 자기가 자르지 못한 사람은 어쨌든 스스로 생각하기에 더 큰 조각을 가져갈 수 있으니 불만이 없겠죠. 문제는 사람의 수가 늘어날 때입니다. 3명만 돼도 슬슬 복잡해지기 시작하거든요.

슈타인하우스가 제시한 3명이 공평하게 나누는 방법은 오른쪽 그림과 같은 ‘고독한 분할법’입니다. 그러나 슈타인하우스의 방법이 유일한 답은 아닙니다. 그 외에도 1960년대 미국 수학자 존 셀프리지와 영국 수학자 존 콘웨이가 비슷한 시기에 각자 발견한 ‘셀프리지-콘웨이 방법’, 1944년 폴란드 수학자 스테판 바나흐와 브로니스와프 크내스터가 개발한 ‘마지막 감축법’도 있죠. 

비교적 최근 연구로는 2016년 4월 호주 수학자 하리스 아지즈와 사이먼 멕켄지가 발표한 논문이 있는데, 이는 사람 수가 n명으로 늘어났을 때 

칼질 안에 공평하게 나눌 수 있다는 내용을 담고 있습니다. 하지만 이렇게 자르면 누가 케이크를 입에 대보기도 전에 케이크가 썩을테니 그냥 좀 불공평해도 적당히 제가 잘라주는 대로 먹기로 하죠. 

     
역동적으로 케이크 자르기
 

휴! 조금 머리가 아팠으니 이번엔 좀 독특한 케이크 자르기 방법을 소개할게요. 1961년 미국 수학자 레스터 더빈스와 에드윈 스패니어가 개발한 이 방법은 축제 분위기에 걸맞은 역동적인 분배법입니다. 

마지막 감축법은 모두 자르는 사람인 동시에 모두 선택하는 사람이 되는 방법인데, 더빈스와 스패니어는 여기에 케이크 위를 움직이는 칼을 적용했습니다. 

한쪽 끝에서 반대쪽 끝까지 바닥에 평행하게 칼이 움직일 때, 원하는 지점에서 참여자가 ‘멈춰라!’ 하고 외치는 겁니다. 그리고 먼저 외친 사람에게 조각을 줍니다. 케이크 분배가 끝날 때까지 남은 사람들은 ‘멈춰라’를 외치고 모든 사람이 케이크를 가지면 분배가 끝나는 식이죠. 동시에 외쳤을 때는 무작위로 사람을 선택합니다. 아주 간단하면서도 손에 땀을 쥐는 케이크 분배법이 되겠죠? 이걸로 게임을 해도 재미있을 것 같네요. 

맛있는 케이크가 눈앞에 있으면 허겁지겁 먹기 바쁜데 이렇게 케이크 분배 문제를 고민한 수학자가 많다는 게 재미있지 않나요? 문제를 떠올리고 풀면서 케이크를 먹는 것보다 즐거워 했을 수학자들의 모습을 상상하니 저도 따라서 미소가 지어집니다. 이번 요리만큼은 여러분도 꼭 따라서 해보세요. 그리고 수학동아 10주년도 함께 축하해주신다면 100점 만점!