d라이브러리

독일 오베르볼파흐 수학연구소는 식당을 지정 좌석제로 운영합니다. 매 끼니마다 다른 사람과 앉아 밥 먹으면서 다양한 교류를 하라는 취지입니다. 그런데 이름이 적힌 냅킨을 무작위로 놓다보면 종종 같은 사람과도 밥을 먹게 됩니다. 매번 다른 사람과 앉을 수는 없을까요?

독일 서남부 지역의 산림지대는 빽빽이 들어선 아름드리나무가 하늘을 가려 흔히 ‘흑림’이라고 부릅니다. 이 외딴 곳에 1944년에 설립한 수학연구소가 있습니다. 독일 오베르볼파흐 수학연구소로, 이곳에서는 매주 다양한 주제로 워크숍이 열립니다.

그런데 원한다고 아무나 갈 수 있는 건 아닙니다. 원하는 주제로 워크숍을 열려면 여러 해 전에 제안서를 제출해 치열한 경쟁을 뚫어야 합니다. 주제가 선정되면 누구를 초대할지 50명 이내로 명단을 작성해 제출합니다. 보통 그 주제의 최고 대가부터 최근에 좋은 결과를 낸 젊은 연구자까지 다양한 수학자를 초대하지요.

필자가 처음 초대받은 건 대학원생이던 2004년이었습니다. 연구소의 명성을 익히 알고 있던 터라 독일에서 국제우편으로 배달 온 초청장을 받자마자 꼭 가겠다고 표시해 팩스로 보냈습니다.

외진 곳에 있는 만큼 연구소를 가는 것도 쉽지 않습니다. 프랑크푸르트 공항에는 기차역이 있어서 지방에 가는 게 쉽지만, 오베르볼파흐 근처에는 고속철도역이 없어 지역 열차로 갈아타 하우자흐역에서 내려야 합니다. 거기서부터는 대중교통도 없어서 택시로 다시 20분을 더 가야 합니다. 운이 좋을 때는 택시가 바로 기다리고 있어서 쉽게 가지만 저는 운이 없는지 택시가 없는 경우가 더 많았습니다.

1명뿐인 시골역 직원에게 영어로 택시 좀 불러달라고 손짓발짓 다 섞어서 하소연했더니 택시 회사에 전화해 줘서 겨우 간 적도 있습니다. 슈퍼마켓도 5km 이상 걸어가야 찾을 수 있습니다. 우리나라로 비유하자면 인천공항에서 강원도 산골짜기까지 외국인 수십 명이 매주 비행기와 기차, 그리고 택시를 갈아타고 힘들게 찾아오는 셈입니다.

수학자의 천국, 오베르볼파흐 수학연구소

미리 연락받은 비밀번호로 현관문을 열고 들어가 보면 방 배정 안내문이 놓여있습니다. 그런데 방에 가면 방문이 그냥 열려 있습니다. 안에 사람이 있을 때만 문을 잠글 수 있습니다. 왜 그럴까요? 호텔이라면 당연히 방문이 잠겨있겠지만 친척집이라면 방 열쇠조차 구경을 못하겠죠? 여기도 마찬가지입니다. 한 가족 같은 수학자들이 모이므로 방 열쇠가 없습니다.

수학자들의 천국이 있다면 이런 곳이 아닐까 생각하게 됩니다. 우선 도서관에 없는 책이 없습니다. 학교에서 구하기 힘들었던 논문이나 책을 쉽게 찾을 수 있을뿐더러 24시간 운영해 아무 때나 이용할 수 있습니다. 게다가 같은 건물에 있는 식당에서는 삼시세끼는 물론 오후 2시 반에 케이크와 커피도 줍니다.

워낙 외진 곳이라 근처에 마땅히 갈만한 곳이 없으니 연구 발표시간을 제외하면 낮이나 밤이나 다들 연습장을 들고 라운지나 식당에 와서 연구를 하거나 다른 사람과 이야기를 나눕니다. 또 그 분야 최고 전문가가 여기 있으니 손쉽게 궁금한 것도 물어볼 수 있습니다. 그러다보면 어려운 문제도 손쉽게 해결합니다.

사람 사귀기도 참 쉽습니다. 점심과 저녁식사는 무조건 자기 이름이 적힌 냅킨 앞에 앉게 되기 때문에 전혀 모르는 사람과도 자연스럽게 인사하고 대화할 기회가 생깁니다. 서로 관심 있는 문제를 이야기하다 보면 때론 뜻이 맞는 사람을 만나 공동연구도 하게 되지요. 물론 식사 때마다 자기 이름이 적힌 냅킨이 어디 있는지 찾느라 한바탕 소동이 벌어지기도 합니다.

연구소 식당에는 원형 테이블이 여러 개 있습니다. 테이블마다 앉을 수 있는 사람 수는 다를 수도 있지요. 천으로 만들어진 냅킨 각각에 방문자 이름표를 붙여놓으면 식사 때 종업원이 냅킨을 아
무렇게나 원형 테이블에 배치합니다.

매 끼니마다 양옆에 다른 사람 앉을 수 있을까?

그런데 자기 자리를 찾고 나면 불평하는 수학자가 꼭 있습니다. 점심에 이 사람 옆에 앉아서 밥을 먹었는데 저녁에도 또 같이 먹게 됐다며 냅킨을 좀 더 잘 섞어서 놓을 수 없냐고 투정을 부립니다. 1967년 이곳을 찾은 독일 수학자 게르하르트 링겔 역시 같은 불만을 표시했던 것 같습니다. 링겔은 다음과 같은 문제를 제기했거든요.

만약 원형 테이블이 m개가 있고 각각의 테이블에 a1, a2, …, am명이 앉는다고 합시다. 참석자가 총 n명이라면 a1+a2+…+am=n이어야 합니다. 이때 참석자 중에서 두 사람을 뽑는 가짓수는 1/2n(n-1)입니다. 이 중 한 명이 저라면 매 식사 때마다 두 명의 수학자가 제 옆에 앉게 됩니다. 각각의 참석자와 정확히 한 번씩 바로 옆에 앉으려면, 저를 뺀 나머지 참석자 수 n-1명을 2로 나눈 총 1/2(n-1)번의 식사 시간이 있어야 합니다. 따라서 이것이 가능하려면 n은 홀수여야만 합니다.

그간 이 문제와 관련해 100개 이상의 논문이 나올 정도로 연구가 활발했습니다. 이런 환상적인 자리 배치가 항상 있는 것은 아니라는 게 이미 알려져 있습니다. 즉 참석자 9명을 두 테이블에 배치하는 OP(4, 5) 문제, 11명을 세 테이블에 앉히는 OP(3, 3, 5) 문제는 답이 존재하지 않는 게 밝혀져 있습니다.

하지만 그 외에는 대부분 답이 있는 것처럼 보입니다. 테이블에 앉을 수 있는 사람 수가 모두 같다면, 즉 a1=a2=…=am이라면 답이 항상 있다는게 1989년 증명됐습니다. 2001년 영국 수학자 안소니 힐튼과 매튜 존슨은 한 테이블에 앉는 사람 수가 1개 빼고 모두 같아도 답이 항상 있다고 밝혔습니다. 2008년에는 캐나다와 폴란드 수학자들이 참석자가 40명 미만일 때 가능한 모든 경우를 컴퓨터를 사용해 따져보니 OP(4, 5)와 OP(3, 3, 5) 빼고는 항상 답이 있다는 걸 밝혔습니다.

2013년에는 이탈리아의 수학자 톰마소 트라에타가 테이블이 2개일 때를 완전히 해결합니다. OP(4, 5)를 제외한 모든 경우에서 a1이 짝수고, a2가 홀수면 항상 환상적인 자리 배치법이 있다는걸 보였지요. 하지만 테이블이 3개만 넘어도 답이 있는지 없는지 모르는 경우가 있었습니다.

2018년 6월 영국 버밍엄대학교 스테판 글록 박사, 펠릭스 요오스 박사, 김재훈 박사, 다니엘라 퀸 교수, 데뤼크 오스투스 교수는 참석자가 충분히 많기만 하면 항상 답이 있다는 걸 증명해 인터넷에 올렸습니다. 앞으로 검증을 기다려야 하겠지만 만약 증명이 옳다면 오베르볼파흐 문제는 이제 유한한 경우를 제외한 모든 경우에 대해 풀린 게 됩니다.

유한한 경우만 남았다고 하니 컴퓨터를 돌려서 확인하면 되지 않겠냐고 물을 수 있습니다. 하지만 참석자가 40명 미만일 때 확인하는 것도 계산 양이 엄청났었습니다. 이번 연구에서 n이 얼마나 커야 하는지는 제대로 언급하고 있지 않지만, 증명을 보면 n은 적어도 지구 전체의 인구보다는 훨씬 큰 수라는 것이 확실합니다. 따라서 이 연구가 옳다고 하더라도 남아 있는 유한한 경우를 푸는 일은 만만치 않아 보입니다.

엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재는 KAIST에서 강의와 연구를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐습니다.