[생활속의 수학] 컴퓨터 1200시간 돌려 푼 '4색 문제'

1852년 영국의 대학원생이었던 구드리는 영국 지도를 색칠하다가 "지도상에서 서로 인접한 영역을 서로 다른 색으로 칠하기 위해서 최소한 몇 가지 색이 필요할까"는 의문을 갖게 됐다.

구드리는 영국 지도의 경우 네가지 색으로 가능하다는 것을 알았지만, 지도의 모양이 아주 복잡해지면 어떻게 될지에 대해서는 확신이 없었다. 이렇게 시작된 '4색 문제'는 점차 세상에 알려지면서 많은 에피소드를 만들었다.

영국의 한 수학자는 이 문제의 해법을 미국 수학 논문집에 발표, 그 공로로 영국 학술회원으로 선출됐고 영국 왕실로부터 작위까지 수여 받았다. 그러나 10여년 후 이 논문에 결정적인 오류가 있음이 밝혀지기도 했다.

1922년 프랭클린은 25개 이하의 구역으로 나뉘어진 지도는 네가지 이하의 색으로 칠할 수 있음을 증명, 4색 문제 해결의 실마리를 제공했다. 이어 27, 35, 39개 이하의 구역에 대해서 네가지 이하의 색이면 가능하다는 식으로 확장해 갔으나, 이러한 접근 방식은 원천적으로 한계를 가질 수밖에 없었다.

4색 문제를 해결하기 위한 노력은 공간의 추상적인 연결상태를 연구하는 '위상(位相)수학'이라는 새로운 분야를 정립시키는 공헌을 했다. 위상수학은 어떤 대상을 연속적으로 변형시킬 때 불변으로 남아있는 성질을 연구하는 현대수학의 한 분야다.

76년 미 일리노이대의 하켄과 아펠은 새로운 방법을 썼다. 이들은 지도의 모양에 따라 나타나는 수많은 경우들을 1천4백76가지로 유형화했다. 인간이 일일이 각 경우를 칠해본다면 한없는 세월이 걸리기 때문에, 컴퓨터를 동원해 분석했다.

1천2백시간 동안 컴퓨터를 돌린 결과 인접한 영역을 다른 색으로 칠하기 위해서는 네가지 색이면 충분하다는 결론이 났다. 1백50년 동안 논란이 되어온 4색 문제는 이렇게 일단락돼 컴퓨터만이 해결할 수 있는 최초의 수학 문제가 됐다.

박경미 홍익대 수학교육과 교수