Four-Colorist

각의 삼등분 작도만큼이나 수많은 아마추어 수학자들의 호기심을 끄는 문제가 바로 4색 문제(Four Color Problem)가 아닐까 싶다.

평면에 그린 어떤 지도도 네 개의 색으로 모든 나라를 구별되게 칠할 수 있다는 이 문제는, 이해하기는 쉬우면서도 증명은 쉽지 않은 데다, 컴퓨터를 이용하고서야 증명에 성공한 것으로 더욱 유명하다.

뇌입원 지식즐 같은 곳을 보면, Appel과 Haken의 컴퓨터를 이용한 증명에 대해 별별 해괴한 소리들이 난무하고 있는데, 간단히 정리해 둘 필요가 있을 것 같다.

우선, 현재 수학자들은 Appel과 Haken의 증명을 올바른 증명으로 인정하고 있다. 컴퓨터를 썼기 때문에 인정을 받지 못했다는 둥 하는 소리는 증명이 막 발표되었던 30년전인 1970년대의 이야기이다. 지금은 이보다 더 무지막지하게 컴퓨터를 사용한 증명이 수도 없이 많다.

물론 일부 수학자들이 컴퓨터를 쓰지 않는, 또는 컴퓨터를 덜 쓰는 증명을 연구하고 있는 것도 사실이지만, 그렇다고 해서 Appel과 Haken의 증명 자체를 인정하지 않는 것은 아니다. 그러니 "4색 문제는 아직 미해결 문제이다"라는 말은 그야말로 뭘 모르고 하는 소리가 되겠다.

또, Appel과 Haken의 증명이 단순히 모든 지도를 컴퓨터로 일일이 확인하는 수준이라고 폄하하는 사람도 있다. 여기서 "모든 지도"는 무한히 많은 가능성이 있고, 이렇게 무한히 많은 경우를 유한 개의 경우만 생각하면 충분한 것으로 줄이는 그 과정에 바로 수학이 필요하다.

4색 문제의 증명을 기념한 우체국 소인

문제가 쉽다 보니 4색 문제를 풀었다고 주장하는 사람을 흔히 보게 되는데, 대부분의 경우 증명이라는 것이

평면에 그린 지도에서 어떤 다섯 나라도 서로 맞닿아 다섯 개의 색을 칠해야 하는 경우는 존재하지 않는다. 따라서 다섯 나라씩 네 개의 색으로 칠하면 모든 지도를 칠할 수 있다.

라는 주장에 바탕하고 있다. 언뜻 보기에는 그럴 듯해 보인다. 어떤 다섯 나라를 골라도 항상 네 개 이하의 색으로 칠할 수 있다면, 지도 전체도 "당연히" 네 개 이하의 색으로 칠할 수 있을 것 같다. 그래서 열심히 경우를 나누어 증명도 하고.

혹시 이런 식으로 4색 문제를 증명하였다고 가슴 두근거리고 있는 분이 있다면 잘 들으시라.

먼저 평면에 그린 지도에서 어떤 다섯 나라를 골라도 항상 네 개 이하의 색으로 칠할 수 있다는 것은 이 문제가 나오자마자 De Morgan이 간단하게 증명하였다. 많은 아마추어들이 이 부분을 여러 경우로 나누어 꽤나 길게 증명하는데, De Morgan의 증명은 서너 줄이면 충분하다.

De Morgan이 증명하였는데도 Appel과 Haken의 증명이 나올 때까지 120년이 넘게 걸렸던 것으로도 알 수 있지만, 어떤 다섯 나라도 항상 네 개 이하의 색으로 칠할 수 있다는 사실이 4색 문제를 증명하는 것은 아니다. (그러니까 가슴 두근거리고 있는 사람들은 꿈깨라는 말이다!)

이 주장이 왜 틀렸는지는 오른쪽 그림을 생각하면 된다. 4색 정리 자체는 참이므로 저 주장의 반례로서 다섯 개의 색이 필요한 지도 따위를 만들 수는 없지만, 저 주장을 약간 바꾸어

어떤 네 나라를 골라도 항상 세 개 이하의 색으로 칠할 수 있다면 지도 전체를 세 개 이하의 색으로 칠할 수 있다.

라는 주장을 생각해 보자. 여섯 나라로 이루어진 오른쪽 그림에서 어떤 네 나라를 골라도 항상 세 개 이하의 색으로 칠할 수 있다. 그렇지만 저 지도는 분명히 세 개 이하의 색으로 칠할 수 없다. 심지어 저 지도는 어떤 다섯 나라를 골라도 세 개 이하의 색으로 칠할 수 있을 정도다.

놀라운 방법으로 4색 문제를 풀었다고 생각하셨던 분들, 이제 이런 문제 푸는 데 시간 낭비하지 마시길.