d라이브러리

큰일 났습니다. 지난번 떡국 시식 후 김우현 기자가 체하는 바람에 수학동아 팀에서 시식요원 기피 현상이 일어났습니다. 그래서 이번에는 믹스만 있으면 누구나 만든다는 팬케이크에 도전했습니다. 무사히 성공할지, 팬케이크에는 어떤 수학이 있을지 한번 보시죠.

바닥이었던 신뢰나마 회복하려면 이번 요리가 잘 돼야 할 텐데 어쩌죠? 원래 상상했던 예쁜 모양은 이미 글렀지만, 처음부터 ‘탑’이 콘셉트였던 것처럼 크기를 맞춰 쌓아야겠어요. 그런데 시간이 없습니다. 팬케이크는 식은 죽 먹기일 줄 알고 미리 시식 요원을 불러뒀다고요! 지금 오고 있을 텐데 최소한의 횟수로 재빠르게 쌓으려면 어떻게 뒤집어야 할까요? 

집안일 하다 떠올린 팬케이크 문제
마침 이 문제를 먼저 고민한 수학자가 있습니다. 미국 수학자 제이콥 굿맨은 1975년 어느날 빨래를 개다가 재미있는 문제를 떠올렸습니다. 수건을 개어 쌓던 굿맨은 마지막 더미가 엉망인 것을 보고 접어둔 수건을 크기에 맞게 다시 정렬해야겠다고 생각했습니다. 큰 수건이 아래에, 작은 수건이 위에 오도록 말이죠. 
그런데 이미 방이 가득 차서 새로 더미를 만들 자리가 없었습니다. 굿맨은 이미 만든 수건 더미를 뒤집어 가며 순서를 맞추기로 했습니다. 그러는 동안 흥미로운 질문이 떠올랐습니다. 
‘최악의 경우 몇 번이나 뒤집어야 차례대로 정렬할 수 있을까?’ 
굿맨은 이 문제를 수건에서 팬케이크로 바꿔 미국의 수학 학술지 ‘미국 월간 수학’에 보냈습니다. 이후 수학자들 사이에서 난제로 유명해지면서 여러 파생 연구를 낳게 됐죠. 

우리 식당 주방장은 솜씨가 엉성해서 팬케이크를 구우면 늘 크기가 다르게 나온다. 그래서 언제나 손님에게 가져가는 길에 큰 팬케이크가 아래로, 작은 팬케이크가 위로 향하게 내가 다시 정렬한다. 위에서부터 몇 장씩 집어 뒤집는 방법을 반복해서 팬케이크를 쌓을 때, 최악의 경우 n개의 팬케이크를 최소 몇 번 뒤집어야 할까?

굿맨이 미국 월간 수학에 보낸 실제 문제의 내용입니다. 좀 더 쉽게 이해하기 쉽게 팬케이크가 3장 있을 때를 예로 들어보겠습니다. 크기가 다른 3장의 팬케이크가 쌓여있는 경우의 수는 아래 그림처럼 3!(3×2=6)가지입니다. 각각 몇 번 만에 ❶번 모양으로 뒤집을 수 있는지 생각해보세요. 

먼저 첫 번째는 기준값으로, 이미 순서대로 정렬돼 있으므로 뒤집는 수는 0입니다. 두 번째 경우에는 위에서 두 번째 팬케이크에 뒤집개를 넣어 위아래로 뒤집으면 한 번에 정렬되므로 뒤집는 수는 1, 세 번째 경우에는 맨 아래 팬케이크에 뒤집개를 넣어 한 번에 정렬할 수 있으므로 뒤집는 수는 1, 같은 방법으로 나머지 팬케이크도 뒤집는 수를 찾을 수 있습니다. 마지막 여섯 번째 팬케이크 더미의 뒤집는 수는 얼마일지 직접 계산해보세요. 

빌 게이츠도 도전한 팬 케이크 문제
구하셨나요? 위 그림을 보면 알 수 있듯 여섯 번째 경우의 뒤집는 수는 3입니다. 팬케이크 문제의 뒤집는 수는 최소 횟수 중에 가장 큰 수를 기준으로 하므로 3장의 팬케이크 문제의 뒤집는 수는 3입니다.   
팬케이크 수가 늘어나면 훨씬 더 어려워지겠죠? 과연 n장일 때 최소 횟수를 바로 계산할 수 있는 일반화 방법이 있을까요? 여러 수학자가 이 방법을 찾기 위해 팬케이크 문제를 연구했지만 더 효율적인 방법으로 줄여나갈 뿐, 정확한 답을 찾지 못했습니다. 심지어 마이크로소프트 설립자 빌 게이츠도 이 문제에 도전했답니다. 
빌 게이츠는 미국 하버드대학교 수학과 출신인데, 유일하게 남긴 수학 논문이 바로 팬케이크 문제에 관한 것입니다. 게이츠는 1979년 발표한 논문에서 n장일 때의 뒤집는 수의 상한값을

 로 제시했고, 이후 30년이나 지난 2009년 미국 텍사스대학교 연구팀이 

로 개선했습니다. 하지만 이것 역시 정확한 답은 아니었죠.   

팬케이크 문제는 NP-난해

빨래를 개다 장난스럽게 만든 문제의 답을 이렇게 찾기 어렵다니! 도무지 풀리지 않던 팬케이크 문제는 2011년에 발표된 연구로 새로운 국면을 맞았습니다.
프랑스 국립과학연구센터(CNRS)의 로랑 뷜토, 기욤 페르틴, 이레나 루수가 ‘팬케이크 뒤집기는 어렵다’는 제목의 논문에서 팬케이크 문제가 다항식으로 나타낼 수 있는 단계 안에 효율적인 알고리듬을 찾을 수 없는 ‘NP-난해’라는 것을 증명한 겁니다. ‘NP-난해’는 경우의 수를 직접 따져보는 것 말고는 수학적으로 일반화한 답을 찾을 수 없는 문제를 뜻합니다. 일이 미흡한 주방장을 둔 웨이터는 불쌍하게도 결코 효율적인 방법을 찾지 못한 채 영원히 복잡하게 팬케이크를 뒤집어야 한다는 뜻이죠. 
하지만 정확한 일반식을 구할 수 없다고 해도 팬케이크 문제의 원리는 불규칙한 데이터를 정렬하는 컴퓨터과학에서 필요한 부분이므로 더 효율적인 알고리듬을 찾는 연구는 계속 이어지고 있습니다. 
또한 기본 팬케이크 문제 말고도 ‘까맣게 탄 면이 있는 팬케이크가 섞여 있을 때 큰 팬케이크가 아래로 가되 항상 탄 면은 바닥면이 되도록 배열해야 한다’는 상황을 추가한 ‘탄 팬케이크 문제’, 팬케이크 대신 인도 빵인 로띠로 변형하고 ‘처음에 한 더미로 쌓여있던 로띠를 불에 구워가며 정렬한다’는 규칙을 추가한 ‘쌍둥이 팬케이크 쌓기 문제’ 같은 발전형 문제가 생겨 여러 분야에 활용되고 있죠. 자기 문제는 풀지 못했지만, 이 정도면 문제의 주인공인 웨이터도 위로가 되지 않을까요? 
이런, 탄 냄새가 나고 있어요! 팬케이크 문제를 알아보다가 숙명처럼 탄 팬케이크 문제를 풀어야만 하게 생겼습니다. 어서 요리를 마무리해야겠군요.

재미있는 건, 팬케이크 문제를 발표할 때 굿맨은 ‘제이콥 굿맨’이라는 자신의 이름 대신 ‘해리 드웨이터’라는 가명을 썼다는 겁니다. 당시 한창 수학자로서 명성을 쌓아가던 굿맨은 사람들이 자신을 하찮은 퍼즐에나 관심 있는 수학자라 생각할까 봐 이름을 바꿨다고 하네요. 팬케이크 문제가 이렇게 중요하고 유명한 문제로 떠오를지 꿈에도 몰랐던 거죠. 저도 부끄러워서 피터팍이라는 별명 뒤에 숨어서 요리하고 있지만, 혹시 압니까, 언젠가 대요리사가 돼서 본명 대신 피터팍으로 유명해질지! 1재미있는 건, 팬케이크 문제를 발표할 때 굿맨은 ‘제이콥 굿맨’이라는 자신의 이름 대신 ‘해리 드웨이터’라는 가명을 썼다는 겁니다. 당시 한창 수학자로서 명성을 쌓아가던 굿맨은 사람들이 자신을 하찮은 퍼즐에나 관심 있는 수학자라 생각할까 봐 이름을 바꿨다고 하네요. 팬케이크 문제가 이렇게 중요하고 유명한 문제로 떠오를지 꿈에도 몰랐던 거죠. 저도 부끄러워서 피터팍이라는 별명 뒤에 숨어서 요리하고 있지만, 혹시 압니까, 언젠가 대요리사가 돼서 본명 대신 피터팍으로 유명해질지! 

참고자료

Simon Singh ‘Flipping pancakes with mathematics’, Laurent Bulteau·Guillaume Fertin·Irena Rusu
‘Pancake Flipping is hard’