본문 바로가기
정신체조수학

4색 문제(four color problem)

by mathpark 2015. 5. 13.

1852년 10월, 영국 런던에 있는 유니버시티 대학(University College)의 대학원생 프렌시스 구드리에(Francis Guthrie)는 영국 지도를 색칠해 나가다가 '인접한 구획들이 같은 색으로 칠해지는 경우가 없게 하려면 최소한 몇 가지의 색이 필요할까?'라는 의문을 갖게 되었다.
결국 영국의 지도에 있는 지역들을 구별하여 색칠하는 데는 4가지 색이면 충분하다는 사실을 알게 되었다. 그는 임의의 구획으로 나누어져 있는 지도를 칠할 때 4가지 색이면 대부분 되는 것 같았지만 확신을 가질 수는 없었다.

다섯 가지 이상의 색을 사용해야 조건에 맞게 그릴 수 있는 지도가 존재할까, 아니면 네 가지 색이면 어떤 지도에서도 인접한 구획들이 다른 색으로 칠해질 수 있음을 증명할 수 있을까?

구드리에는 런던 대학의 학생이었던 남동생 프레더릭한테 물었고, 프레더릭은 다시 스승인 모르간(Augustus De Morgan)에게 물었다. 모르간은 또 아일랜드의 수학자이자 위대한 물리학자였던 해밀턴(William Rowan Hamilton)에게 편지를 썼다. 해밀턴도 다섯 종류의 색이 필요한 도형을 찾지 못했으며, 그런 도형이 존재하지 않는다는 것을 수학적으로 증명할 수도 없었다.
그 뒤 이 문제는 빠른 속도로 유럽에 전파되어 여러 사람들의 도전을 받았지만, 내노라하는 수학자들도 증명하지 못했고, 1878년 케일리(F. Cayley)에 의해 공식적으로 제기되었다.

4색 문제(four color problem)로 불리는 이 문제는 1879년 영국의 켐페(Alfred Bray Kempe)에 의해 풀렸다. 그렇게 알고 있었다. 그러다가 1890년, 더럼 대학의 강사였던 존 하우드(Percy John Heawood)는 켐페가 해결한 것으로 알려진 논문에서 오류를 발견했고, 이를 수정하여 다섯 종류의 색으로는 모든 지도를 칠할 수 있다는 결론을 내렸다. 이런 연구 과정에서 위상수학(topology)라는 새로운 분야의 수학이 크게 발전하였다.

1922년, 필립 프랭클린(Philip Franklin)은 25개 이하의 구획의 도형은 4개 이하의 색으로 칠할 수 있음을 증명하였다. 1926년, 레이놀드(Reynolds)는 27개 구획으로 증명의 대상을 늘리는데 성공했다. 1940년, 빈(Winn)은 35개 구획, 1970년, 오르(Ore)와 스템플(Stemple)은 39개 구획으로까지 증명했다. 하지만, 이런 식의 방법으로는 무한히 많은 구획을 다룰 수는 없을 것이다.

1976년, 미국 일리노이 대학의 볼프강 하켄(Wolfgang Haken)과 케네스 아펠(Kenneth Appel)은 새로운 테크닉을 개발했다. 그들은 '유한한 구획으로 나뉘어져 있는 유한한 개수의 지도들로부터 무한히 많은 구획으로 나뉘어진 무한개의 지도들을 유추해 낼 수 있다'고 주장했던 하인리히 히쉬(Heinrich Heesch)의 업적을 줄곧 연구해 왔었다. 히쉬는 유한한 개수의 지도만으로 일반적인 경우를 다룰 수 있는 방법을 개발해 내었다. 하켄과 아펠은 4색 문제를 히쉬의 아이디어로 단순화시키긴 했지만 그들이 얻은 결과는 '무한히 많은 모든 지도들이 4색으로 칠해질 수 있음을 증명하려면 1,482가지의 유한한 지도들만 고려하면 된다'는 것이었다. 즉, 1,482가지의 지도들이 모두 4가지 색으로 칠해질 수 있음을 증명한다면 그것은 곧 모든 종류의 지도에 대해서도 성립한다는 결론이었다.

이를 증명하려면 대형 컴퓨터를 이용해도 100년 동안은 돌려야 될 정도의 문제였다. 그러나 하켄과 아펠은 이에 대한 불필요한 부분은 계산하지 않게 하는 등의 연구를 하여 1976년 6월, 1,200시간 동안 컴퓨터를 돌려 이를 증명했다. 발표된 증명은 본문과 도해를 담은 대략 50쪽과 2,500개의 또 다른 도해를 담은 85쪽 및 그 증명의 여러 부분에 대한 상세한 설명을 담은 400쪽의 마이크로피시(microfiche)와 함께 액면 그대로 받아들여야만 하는 계산 결과가 포함되어 있다. 아벨과 하켄의 증명은 완벽한 것으로 검증되었지만 지나치게 복잡하고, 기계의 힘을 빌렸으며, 이 문제의 증명 이외에는 쓸모가 전혀 없는 등의 이유로 수학자들을 그리 기쁘게 하지는 못했다.

이것은 우아하고 단순한 방법으로 증명되어야 할 문제로 여전히 남아 있다.





'정신체조수학' 카테고리의 다른 글

간단한(?) 퀴즈 몇 개  (2) 2015.05.14
결혼 공식  (0) 2015.05.13
4색 문제(four color problem)  (0) 2015.05.13
공평한 분배의 방법  (0) 2015.05.13
수를 세는 일상 단위  (0) 2015.05.13

댓글0