4색정리
1. 개요
Four color theorem
인접한 나라끼리 겹치지 않게끔 지도 위의 모든 나라를 색칠하는 데 4가지 색만으로도 충분한지 따지는 문제. 의외로 위상수학과 관련된 문제이다. 자세한건 후술. 4색 지도, 4색 증명 등으로도 불린다.
2. 발단
앞선 시기에 독일의 수학자 뫼비우스가 4색 문제를 먼저 거론했다는 기록이 있긴 하지만, 이 문제가 본격적으로 알려진 계기는 집합과 관련된 법칙으로 더 친숙한 영국의 수학자 드모르간이라는 것이 정설이다.
1852년 영국의 식물학자 프란시스 구스리(Fransis Guthrie)는 영국 지도를 구획 별로 색칠하던 중 4가지 색만 있으면 인접한 지역끼리 서로 겹치지 않게 칠할 수 있다는 것을 깨닫고는, 다른 모든 지도의 경우에도 그러한지 궁금해했다. 프란시스의 동생 프레드릭은 형에게 들은 지도와 4가지 색에 대한 이야기를 저명한 수학자 오거스터스 드 모르간[1]에게 물었는데, 이후 드모르간 본인을 포함하여 수많은 수학자들이 4색 문제에 뛰어들었다.
3. 증명 과정
다른 난제들과 달리 어린아이도 이해할 수 있는 간단한 문제라서, 별 거 아닐거라 얕보고 일반인이고 전문가고 자신만만하게 증명을 시도했다가 낭패를 보는 일이 많았다. 특히 수학자중엔 반평생동안 이 문제에만 줄창 매달렸다가 결국 나가떨어지는 경우도 많았다.
4색 문제를 자신이 해결했다는 사람은 많았으나 대부분은 엉터리였고, 수학자들조차도 한동안 부분적, 간접적 증명에서 더 이상 발을 떼지 못했다. 1879년 알프레드 켐프(Alfred Kempe)가 신박한 증명을 내놓으면서 4색 문제에 종지부를 찍는 듯 보였지만 11년 뒤에 증명 과정의 오류가 밝혀지며 다시 원점으로 돌아오는 일도 있었다. 이 오류를 밝힌 퍼시 히우드(Percy Heawood)는 켐프의 정리를 손질하여 5색으로는 어떠한 지도라도 색칠이 가능하다는 5색 정리를 증명하는 데 성공한다.[2]
1960년대 독일의 헤쉬는 '컴퓨터를 이용해 이 문제를 증명한다.'는 당시로서 아주 획기적인 발상을 하였다. 이에 헤쉬는 증명에 필요한 컴퓨터를 구하기 위해 독일과 미국을 동분서주하며 기초이론을 세웠지만, 패전한 서독의 경제사정 탓이었는지 연구 자금이 부족해 결국 연구를 그만두고 만다. 헤쉬가 만든 경우의 수는 거의 9천 개에 가까웠고, 당시 컴퓨터 성능으로는 이 모든 경우를 시뮬레이션하는 데 10년이 넘게 걸릴꺼라 예상되면서 포기했다고 한다.
4. 컴퓨터를 통한 최초의 증명
1976년 미국의 볼프강 하켄, 케네스 아펠이 헤쉬의 아이디어를 바탕으로 컴퓨터 두 대를 50여 일 가량 돌린 끝에 증명에 성공했다.
이들이 채택한 방법은 컴퓨터를 이용해서 가능한 모든 경우의 지도 모델을 뽑고, 거기에 4색 정리가 적용되는지 안 되는지를 가려보자는 것이다. 컴퓨터를 사용한 브루트 포스이다. 모든 계산이 끝난 뒤에 반례가 하나도 나오지 않는다면 4색 정리는 증명되고, 반례가 나오더라도 그 자체로 4색 정리는 거짓이라고 밝혀져서 4색 문제가 해결되는 매우 간단한 방법이었다. 공식이나 법칙을 모를 때 모든 경우에 대해 직접 쓰거나 그려서 문제를 푸는 것과 근본적으로는 동일하다.
앞서 헤쉬가 기초 이론을 세우던 과정에서 검토해야할 지도의 모델은 9천 개 정도였지만, 하켄과 아펠은 모델을 더욱 단순화시켜 1936개까지 줄였다.[3] 하켄과 아펠은 여기에 487가지 판별 필터를 걸고 컴퓨터 2대를 따로 돌려서 같은 결과가 나옴을 확인한 다음, 컴퓨터로 계산한 자료를 (고등학생, 대학생이던) 자기 아들, 딸에게 직접 축소된 부분을 칠하도록 해 증명했다. 이 때문에 타 논문이었으면 연구비를 지원한 기관에 감사하다는 내용을 썼을 테지만, 이 논문의 첫 시작은 자녀들에게 감사하다는 내용이었다.
이렇다보니 증명 결과만 몇 박스에 달했고, 여러 수학자들 앞에서 멋지게 수식을 휘날리며 결론을 도출한 뒤 과정에 오류가 없음을 확인받는 기존의 증명과 달리 '컴퓨터로 계산해서 빼먹은 것 없는지 확인 다 했고, 그 결과물이 이거다.' 하며 종이 몇 박스를 들이미는 식이라 여러 수학자들에게 '''아름답지 못한 증명'''이라고 까였다.[4] 거기에 최초로 컴퓨터를 사용한 증명이라는 점 역시 인간이 검증할 수 없다는 이유로 기존 수학자들이 반감을 품었다. 실제로 당시 기록들을 살펴보면, '검토 결과 그들의 증명 과정에서 오류가 없음은 반박할 수 없는 사실이지만, 그래도 컴퓨터를 가지고 이런 무식한 방법으로 증명했다는 점에서 까여야 함.' 하며 비판하는 경우가 많았다.
누구나 다 컴퓨터를 가지고 있고 컴퓨터의 속도가 비약적으로 증가해 이 정도 계산은 몇 초도 지나지 않아 끝나는 오늘날에는 '까짓 거 소스 코드 좀 짜고 실행 버튼 누르면 끝이니 수학을 잘 알지 못해도 하겠네.' 생각할 수 있다. 그러나 하켄과 아펠은 수 년에 걸쳐 이론을 가다듬고 계산과정을 최적화하는 데 공을 들였으며, 계산을 수행할 컴퓨터와 연구에 필요한 자금을 얻기 위해 노력했다. 1200여 시간 동안 하드를 불태우며 작업을 수행한 것은 컴퓨터지만, 컴퓨터가 계산을 하도록 모델의 숫자를 줄이고[5] 모든 준비와 검토, 발표를 담당한 하켄과 아펠의 공로를 무시해서는 안 된다.
5. 의의
수많은 수학 난제들이 그러하듯 사실 정리의 증명 자체는 크게 실용성이 없었다. 지도 색칠은 색을 적게 쓰는 것보다는 알아보기 편하도록 적재적소에 알맞은 색을 쓰는 것이 중요하기 때문이다. 그러나 그 과정에서 나온 수많은 중간 결과물들이 다른 난제를 푸는 데 도움이 되거나 새로운 난제를 낳았다. 먼저 이 문제를 통해 위상수학과 그래프 이론이 한층 더 발전할 수 있었다. 실제로 위상수학을 통해 5개 이상 영역이 완전그래프를 이루지 않으면 4색 채색이 충분히 가능함을 증명했고, 역으로 완전그래프를 이루는 꼭지점(영역)의 최대 개수만큼 색상 수를 선택해야 모든 영역을 같은 색상이 인접하지 않도록 그릴 수 있음도 증명했다.[6] 또 복잡한 계산이나 모델화, 검증과 같은 증명 과정에 컴퓨터를 사용하는 것이 일반화하여 이제 컴퓨터는 수학과 뗄 수 없는 도구가 되었다.
6. 제약사항
다만, 이 증명의 의의는 어디까지나 종이 위에서 4가지 색으로 모든 칸을 칠하는 게 가능하다는 이론적인 얘기일 뿐이라 실제 지도에 이걸 써먹는 일은 없다. 애초에 지도의 목적은 보는 사람이 알아보기가 쉽게 만드는 것이지, 색깔 아끼는 게 아니다. 무리해서 4색으로 그려넣는다 해도 5개째부터의 영역을 그래프로 표시하면 앞선 4개와 겹쳐지는 완전그래프를 이루기 때문에 알아보기만 힘들어진다. 이 때문에 필연적으로 색상을 5개 이상 사용해야 한다. 그러니까 실제 지도 제작에서 4가지 색상만 사용하겠다는 건 멘탈 낭비이자 시간 낭비일 뿐이다. 게다가 '''세계지도는 엄밀히 따지면 평면 지도가 아니기에''', 세계지도를 4색정리 증명에 사용할 수는 없다.
우선 연못이나 호수를 바다처럼 푸른색으로 그려야 한다거나, 월경지와 섬을 본토와 같은 색으로 그려야 하는 조건은 지도 채색에 있어서 가장 많이 적용되는 제약사항이다. 월경지를 예로 들자면, 본토 A를 B-C-D가 감싸고, 이를 다시 E가 감싸는 와중에 E 옆에 월경지 A'가 붙어 있는 경우, 결과적으로 A-B-C-D-E가 완전그래프를 이루는 구조이기 때문에 4개 색상으로 칠할 수 없다.
여러 개의 영역이 꼭지점으로만 인접하는 경우는 위상수학에서 토러스로 환원할 수 있기에, 많아야 3개 색상으로 색칠이 가능하지만, 이런 경우를 전부 다른 색상으로 칠해야 한다면 몇 가지 색상을 써도 채색이 불가능하다.
분쟁 지역을 중립적으로 그려야 한다는 조건은 드문 제약사항이긴 하지만, 실제로는 가장 강력한 제약사항이다. 예를 들어 A,B,C,D가 서로 자기네 땅이라 주장하는 e 영역을 중립적으로 그려야 하는 경우는 필연적으로 A-B-C-D-e가 완전그래프를 이룬다. 이러면 당연히 e만을 위한 색상을 새로 채택해야 하기에 4가지 색상으로 그릴 수 없다. A,B 사이에서만 일어나는 분쟁 지역이라 해도 그 관계를 색상으로 표시해야 한다는 제약사항이 있는 경우에는 C에도 D에도 해당되지 않는 색상 ab를 써야 하기에, 이 역시 4색 채색은 물건너갔다고 봐도 된다.
평면 지도가 아닌 입체 지도 역시 4색정리, 나아가 n색정리가 적용되지 않는다. 입체 지도를 위상적으로 변환하면 지하철 노선도와 유사한 형태가 되는데, 이 자체가 n색정리를 적용할 수 없는 구조이기 때문이다.[7] 반면 세계지도(원통 표면), 지구본(구 표면)은 3차원이 아니라 휜 2차원이므로 n색정리가 성립한다. 둘다 정확히 4색이 필요하다.
7. 여담
해당 문제를 해결했던 볼프강 하켄과 케네스 아펠은 다음과 같은 말을 남겼다. #
이와 비슷한 말도 있다.어느 순간부터인가, 컴퓨터가 우리를 놀라게 하기 시작했습니다.
처음에 우리는 계산에 필요한 변수들을 일일이 손으로 입력하면서 작업을 했기 때문에 어떤 상황에서든 컴퓨터의 모든 동작을 미리 예견할 수 있었습니다.
그런데 갑자기 컴퓨터가 체스를 두는 로봇처럼 혼자서 돌아가기 시작했습니다. 컴퓨터는 자신이 '학습했던' 모든 방법들을 하나씩 적용해 나가면서 계산을 했고,
어떤 때는 사람보다도 현명한 판단을 내리곤 했습니다. 그 이후로 우리는 계산을 어떻게 진행해야 할지 컴퓨터에게 배우는 신세가 되었습니다.
어떤 면에서 볼 때 컴퓨터는 계산 능력뿐만 아니라 지적인 능력까지도 자신의 창조주인 인간을 능가하고 있었습니다.
알파고(특히 알파고 vs 알파고)를 경험한 현대인의 입장에서 여러가지로 생각할 거리를 던져주는 말이다.리만 가설이 맞는 것인지 컴퓨터에게 물어보았다고 합시다. 그런데 컴퓨터가 "네, 맞습니다. 그런데 그 이유를 설명한다 해도 당신은 이해하지 못할 것입니다."라 대답한다면, 이 얼마나 황당하고 기죽는 일이겠습니까? ,,
- 사이먼 싱, '페르마의 마지막 정리(Fermat's last theorem)', 박병철 역, 영림카디널, p.399,403
마틴 가드너는 1975년 4월 1일날 자신의 Mathematical Games 칼럼에 다음의 복잡한 지도가 4색 문제의 반례라고 했다. # 물론 날짜를 보면 알듯이 만우절 낚시였다.
용의자 X의 헌신에 나오는 이시가미 데츠야가 더 '아름다운' 방법으로 증명하고 싶다는 문제가 이것이다.
[1] 집합 공부할 때 나오는 그 '''드 모르간의 법칙'''을 만든 사람이다.[2] 참고로 드 모르간은 6색 정리를 증명했다.[3] 하켄-아펠 이후 사람들이 더 연구하여 지금은 이 모델을 633개까지 줄일 수 있다고 한다.[4] 간단히 비유하자면 '1부터 100까지 숫자 중 짝수는 몇 개가 있을까?'라는 문제가 있을 때, '어떤 수를 2로 나눈 몫은 그 수보다 작거나 같은 짝수의 갯수다. 따라서 100/2=50, 50개다.'라는 답이 수학자들이 좋아하는 깔끔한 답이다. 하지만 4색 정리는 사실상 2, 4, 6, 8 이런 식으로 100까지의 짝수를 모조리 써갈기고는 '다 쓰고 세어보니까 50개네요.'라고 하는 거나 다를 바 없었다. 당연히 싫어할만 하다. 실제로 중고등학교 수학시험 중에서는, 주관식 문제의 풀이과정이 무슨 공식을 쓴 게 아니라 이런 노가다식일 경우 감점하는 경우도 있다. 다만 4색정리의 문제점은 '''현재까지 알려진 바로는 후자의 방식의 풀이밖에 없다'''는 것...[5] 앞서 설명했듯 기존에 9천개라고 알려져 있던 모델을 1936개까지 줄인 건 두 사람의 공로다.[6] 꼭지점 5개가 완전그래프를 이루는 경우는 평면 그래프가 아니다.[7] 이는 귀류법으로 간단히 증명된다. n개의 노선을 어떻게 색상을 달리 써서 그렸는데, 그 노선들과 전부 환승이 가능한 노선이 신설되면, 신설 노선을 위해 어쩔 수 없이 또 다른 색상을 사용해야 한다. 'n색정리' 자체가 n개의 색상만을 이용하여 모든 영역을 구분지어 칠할 수 있다고 보는 것인데, 이 경우는 필연적으로 n+1개의 색상을 사용해야 하니 모순이 된다.