d라이브러리

중요한 수학문제들은 실생활에서 별로 쓸모 없는 것처럼 보인다. 최근에 화제를 불러 일으켰던 페르마(Fermat)의 정리(과학동아 94년 12월호)나 괴델의 불완전성 정리(과학동아 95년 1월호) 등은 수학계의 대난제였으나 막상 해결되고 보니 그 내용이 실생활에 직접 쓰이는 일은 없다. 이들과 맞먹을 정도의 난문제로서 4색문제가 있다.
 

사색문제(그림1)는 지도 인쇄업자들이 경험적으로 발견한 것이다. 그들은 평면지도를 만드는 데 4가지 이상의 색이 필요하지 않음을 알았다. 이것이 수학계에 정식으로 등장한 것은 1852년 10월 23일의 일이다. 당시 런던대학 교수였던 드 모르강(A. De Morgan 1806-1871)이 영국 수학계의 대부인 해밀턴(W.R. Hamilton 1805-1865)에게 다음과 같은 편지를 썼다.

"나의 학생이 다음과 같은 사실에 관해 질문했습니다. 나는 그것이 옳은 것인지 여부를 알 수 없습니다. 즉 '평면도형을 어떤 방법으로 나누어 각 부분이 다른 색을 갖고 공통의 경계선을 갖는 부분을 다른 색으로 할 때 4종류의 색만이 필요하며 그 이상의 색은 불필요하다. 즉 5색 이상 필요한 지도는 없다'는 내용입니다."

수학자들이 1백25년간 도전한 문제

해밀턴은 4원수(元數)의 발견자다. a, b, c, d를 실수로 할 때 2원수는 복소수 a+bi, i²=-1이고 4원수는 a+bi+cj+dk(i²=j²=k²=-1, ij=-ji=k, jk=-kj=i, ki=-ik=j)라는 성질을 갖는다.

4원수의 창시자인 해밀턴은 4색문제에 대해 반응이 냉담했다고 전해진다. 드 모르강에게 처음 이 문제를 질문한 학생은 그 후 에든버러 대학의 물리학 교수가 된 가스리(F. Guthrie)로 알려져 있다. 이 문제를 생각한 것은 수학자가 된 그의 형이었다. 이들 형제는 물리학, 수학자였으나 과학자로서의 업적은 별로 알려져 있지 않다. 다만 4색문제 제출자로서의 이름만을 수학사에 남겼을 뿐이다.

19세기 최대 수학자의 하나인 민코프스키(H. Minkowski 1864-1909)는 강의중 "이 문제가 아직 풀리지 않는 것은 3류급의 수학자들이 도전해 왔기 때문이며, 내가한다면 금방이라도 증명할 수 있을 것이다"라고 큰소리 쳤다. 그러나 그는 그 후 "교만해 벌을 받았다. 나도 풀 수 없다"라고 고백했다고 전해진다.

이 문제가 제출된 후 1976년까지 1백 25년간 수많은 수학자가 도전했다. 또 수많은 이야깃거리를 남겼던 이 문제는 자칫하면 큰 함정에 빠질 수 있었다. 수학사상의 난문제란 되도록이면 간단해야 많은 화제를 일으킨다. 겉보기에 간단해야 수많은 사람이 유혹돼 덤비기 때문이다.

많은 사람들이 4색문제를 해결했다고 주장해 왔으나 바로 증명에 미비점이 있음이 발견됐다. 1976년 마침내 증명됐으나, 그 내용은 이상하고 종래의 수학개념으로는 도저히 '증명'이라고 할 수 있는 성질의 것이 아니었던 것이다. 실제 지도작성에 있을 수 있는 가능성을 2천개 정도로 분류하고 당시의 컴퓨터로 그것을 일일이 하나씩 조사하는 데 몇천 시간이나 소요됐는데, 그 내용은 일류수학자가 평생동안 읽는다 해도 다 못읽을 것이다. 그 후 그보다 더 좋은 방법이 있을 것이라는 주장이 나왔으나 시도하는 사람은 아무도 없었다.

수학에서 좋은 문제란 다른 분야와 많은 관련이 있다. 4색문제는 수학의 주류에서 상당히 벗어난 고립적인 성질의 것이다. 따라서 그 풀이에 성공했어도 큰 부산물은 별로 없었다. 하지만 수학자를 유혹할 만큼의 재미는 있었다. 또한 '수학이란 무엇이냐', 또는 '증명이란 무엇이냐'라는 철학적인 의미를 남겼다.

"왜 이 문제에 도전하는가"라고 물으면 으레 '그곳에 문제 (산)가 있기 때문이다"라고 으스대왔던 고대 그리스 이래의 주지주의적 신념도 이 엄청난 작업 끝에는 겁이 날 수밖에 없었을 것이다.

수학 증명방법의 하나 귀류법
 

처음으로 사색문제를 시도한 드 모르강은 5개 나라의 지도를 그리는 데 5가지 색은 필요없을 것처럼 보았다. 물론 그것만으로 완전한 답이 될 수는 없다. 그렇다고 해서 색 종류를 3색으로 제한하면 성립되지 않음이 금방 나타난다.

1879년 켐페(A.B.Kempe, 1849〜1922)가 4색문제의 증명을 발표했다(그림2). 그것은 교묘한 수법이었고 그 후 10년동안 그 증명이 완성된 것으로 믿어져 왔다.

그의 증명은 '켐페의 골'을 이용한 것이었다. 적색 청색 황색 녹색 4가지의 색깔로 그려진 지도에 대해서 가령 적색과 황색으로만 이루어진 나라만을 주목하려면 그 나라들은 청색과 녹색의 바다 속에 몇개의 섬으로 돼 있어야 한다(단 섬 속에 호수가 있고 호수 속에 섬이 있다).

이와 같은 섬 하나하나가 켐페의 골이다. 적색과 황색의 연쇄로 된 섬에서 적색과 황색을 바꾸어도 인접하는 나라의 색이 같아질 수는 없다. 지도를 4종류의 색으로 그려갈 때 한곳에서라도 색깔이 겹치게 되면 이미 색칠한 부분 가운데 적당한 켐페의 골의 색을 바꾸어 간다는 것이다.

수학 증명 방법의 하나로 귀류법(歸謬法)이 있다. 처음 그릇된 가정에서 출발해 모순을 유도함으로써 처음의 과정이 잘못돼 있음을 증명하는 것이다. 이 방법을 4색문제에 적용하기 위해 처음 5가지의 색이 필요하다고 가정해 논리를 진행한다. 이러한 모순을 야기하는 지도 가운데 최소의 개수를 갖는 모순된 지도에 대해서 조사해 그런 경우가 있을 수 없음을 주장한다.

켐페의 증명은 최소 개수의 모순을 야기하는 지도(최소 모순지도)에 대해서 그들 나라 가운데 하나를 한 점에 수렴시키면 나라의 개수가 한 개 줄어들기 때문에 4색으로 그려넣을 수 있게 되며, 그것을 그린 방법을 적당히 바꾸고 수축된 나라를 한 개의 위치로 바꾸어도 4색으로 그릴 수 있도록 하는 것이다. 가령 다른 3개국과 인접하는 삼각형의 나라가 있다면 그것을 수축시킨 4색으로 그리는 방법에서 원래의 지도에 대해 색칠하기가 가능해진다.
 

4각형의 나라를 수축시킨 경우도 켐페의 골로서 색바꿈에 의해서 원래의 지도에 대해 색칠하기가 가능해진다. 모든 지도에 관해서 3각형 4각형 5각형으로 바꾸어 생각할 수 있으므로 마지막 단계에서 5각형 나라의 경우를 수축시키는 방법을 생각하면 된다. 켐페는 4각형의 경우와 같이 해서 가능하다고 주장했다. 그러나 1890년 켐페가 주장한 5각형의 경우에 관해서는 오류가 있음이 발견됐다(그림3).
 

드디어 이 문제는 위상수학(位相數學)의 영역으로까지 파고들고 여러 위상적인 곡면에 대해 일류 수학자들이 도전했다. 이는 평면상의 4색문제로 원환(圓環)에서는 7색(그림4), 뫼비우스의 띠에서는 6색문제(그림5)가 된다.
 

가약배치의 불가피집합
 

1922년 26개 이하 나라의 지도에 대해서는 4색으로 그릴 수 있음이 증명됐다(그림6). 여기에는 가약배치라는 것이 등장한다. 배치란 각 나라의 인접상황을 나타내는 것이며, 가약이란 그것을 포함하는 어떤 지도도 최소 모순 지도가 될 수 없다는 것이다. 켐페는 3각형 한 개, 또는 4각형 한 개로 된 것이 가약임을 증명했던 셈이다.

결국 4색문제는 모든 지도, 또는 적어도 최소 모순지도가 가약배치를 내포함을 증명하는 문제에 귀결됐다. 그 방법은 가약배치 집합의 '불가피성(不可避性)' 즉 어떤 지도도 그 집합내 어느 하나의 배치를 포함해야 된다는 것이다.

헤시(H.Heesh)는 1936년에서 시작해 40년간 4색문제만을 연구했다. 그는 수많은 좋은 착상을 했고 실제 4색분야의 해결에 결정적인 역할을 했다. 그러나 그 문제의 해결은 제자인 하켄(W.Haken 1928- )에 의해 빼앗겼다. 그것은 미담이 아니라 비극이었다. 즉 제자가 스승의 업적을 이어받아 그 사후에 완성시킨 것이 아니며 사제간의 싸움으로 서로 갈라선 후에 이루어진 것이다.

1950년 헤시는 처음으로 가약배치의 불가피집합을 발견했으며 그 개수는 약1만개의 배치다. 그는 또 가약성을 확인하는 계산프로그램을 작성했다. 헤시는 전하(電荷)의 방출과 유사한 방법으로 불가피성을 증명할 것을 생각했다. 방전법이란 적당히 +-를 띤 같은 양의 전하를 중화시키는 기법이다.

지도상에는 각 나라에 적당히 전하가 주어져 있고, 그것이 일정한 규칙에 따라 이웃나라에 넘겨진다. 가령 5각형 나라의 전하는 그 인접국 중 6각형 이상의 것에 넘겨진다. 이때 배치가 주어져 있는 지도에 대해서 전하가 서로 상쇄되도록 생각하는 것이다. 이 방전구조는 집합의 복잡성과 일치한다.

방전법을 실시하는 데는 컴퓨터를 동원할 수밖에 없었다. 아펠(K.Appel)과 앞서 등장 한 하켄에 의해 1975년 일리노이 대학의 계산기 IBM360의 기계어로 가약성판정의 계산프로그램이 쓰여졌다.

1976년 1월 불가피집합의 구조를 밝히기 시작했다. 일일이 여러가지 경우에 대해 계산기로 확인하면서 진행하는 데 무려 6개월이나 걸렸다. 4색문제를 마지막으로 굴복시킨 아펠과 하켄의 이름은 영원히 수학사에 남을 것이다. 하지만 인간의 지성과 계산기의 증명에 관한 논의는 앞으로도 수학계의 큰 문제로 남게 됐다.

인간의 힘으로는 도저히 확인할 수 없는 방대한 작업을 일일이 증명해 낸 계산기. "과연 이 결과를 인간이 정리할 수 있을까"라는 의문이 철학자, 수학자들로부터 제기됐다.

"계산기는 절대로 실수하지 않는가?"
이 사실을 확인할 수 있는 사람은 아무도 없다.