오늘의유머 - 4색문제를 풀어보자

0. 기원

4색문제(혹은 4색정리) 는 1852년에 제기된 것으로 알려져있는데, 사실 문제는 굉장히 단순해서, 인류가 존재한 이후 언제라도 제기될 수 있었던 문제입니다. 19세기 이전에 단지 수학자 사회에 알려지지 않았을 뿐 아니었을까 하는 생각이 듭니다.

1852년 드모르간이 해밀턴에게 편지를 한 통 보내는데 내용이 다음과 같습니다.

A student of mine asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured - four colours may be wanted, but not more - the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented. ...... If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphynx did....

제가 가르치고 있는 한 학생이 오늘 저조차도 답을 알 수 없는 질문을 해왔습니다. 임의의 구획들로 나뉘어져 있는 도형을 칠해나갈 때, 인접한 구획들이 동일한 색상으로 칠해지는 경우가 하나도 없도록 칠하려면 네 종류의 색상만 갖고도 충분한가? 그 학생의 질문은 이런 내용이었습니다. 몇 가지 도형을 그려놓고 테스트를 해 보았더니, 두 개, 세 개, 혹은 네 개의 색상으로 목적을 달성할 수 있는 경우뿐이었습니다. 그런데 다섯 개 이상의 색을 사용해야만 목적을 이룰 수 있는, 그런 도형이 과연 존재할까요? 만일 당신이 아주 간단한 방법으로 도형을 찾아낸다면 저는 그 자리에서 멍청한 바보였음이 판명되는 셈입니다. 그렇게 되면 저는 스핑크스가 했던 것처럼...

(번역본은 박병철님이 옮긴 페르마의 마지막 정리에서 가져왔습니다.)

글로 말하면 되게 길어지는데 간단히 말해서,

이렇게 인접한 두 지역의 색을 다르게 칠한다고 하면, 몇가지 색이 필요하느냐가 질문입니다.

이 도형을 보면, 모든 지역이 붙어있으므로 모두 다른 색으로 칠해져야 됩니다. 자, 그러니까 어떤 지도는 최소한 네 가지 색이 필요함은 알았습니다. 그러면 다섯가지 색이 있어야만 칠할 수 있는 지도가 있느냐? 즉, 모든 지도가 4색으로 충분하냐는 질문이 4색문제입니다.

1. 이 글의 목표

페르마의 마지막 정리의 경우, 난제이고, 일반인도 쉽게 이해할 수 있지만, 그 문제풀이(앤드류 와일즈의 그것)는 일반인은 커녕 수학과 학부생도 뭔 소린지 알아들을 수 없죠. 그저 정수론 교재 뒷면에 부록 정도를 보면서 타원곡선이 무엇인지 페르마의 마지막 정리랑 어떤 상관이 있는지 알아볼 수 있는 정도. 4색문제는 수학난제중 하나이면서, 일반인이 이해할 수 있으면서, 그리고 일반인도 그 풀이를 이해할 수 있는 문제중 거의 유일한 문제중 하나입니다.

그런데 4색문제에 대해 많은 글들이 있지만 문제풀이의 핵심 아이디어를 일반인들에게 설명하는 것은 많이 부족합니다. 일반인을 타겟으로 한 대부분의 글들이 ‘유한한 케이스로 만들어 컴퓨터에 집어넣어서 증명시켰다’ 정도에서 끝납니다. 그렇게 설명하면 어떻게 그걸 유한한 케이스로 만드는지에 대해서 의문이 들게 되죠. 네이버 수학산책의 4색 정리 글이 그나마 reducible에 대해서 설명하려고 했지만, 그래프의 개념을 도입하지 않으려 하다 보니 충분한 설명이 되지 못했습니다. 경문수학산책에서 4색문제를 조금 자세하게 다루지만 일반인이 관심을 가지고 읽기에는 힘들게 써 있고요. (아무래도 4색문제의 특성상, 글만 가지고는 설명이 어렵습니다..)

이 글의 목표는 일반인이 이해할 수 있다면, 정말로 해 보자! 입니다. 즉 정규교육과정을 충실히 이행한 일반인의 수준에서 4색문제를 최대한 깊게 팔 수 있는만큼 파서 이해해보자는 것입니다. 그래서 여러분이 어디가서 4색문제 해서 겁나 유식하게 설명할 수 있도록 만드는 것이 이 글의 목표입니다.

1부(이 글)에서는 4색문제를 이해해보고, 그것이 그래프 문제로 어떻게 바뀌는지 정도까지 알아보고, 2부에서는 문제 풀이의 기본아이디어를, 그리고 마지막으로 3부에서는 그 아이디어를 바탕으로 실제로 어떻게 풀어졌는지에 대해 알아보고 마치려고 합니다.

2. 암묵의 룰 하나

4색문제에서 ‘나라’ 라고 부르는 것은 연결된 하나의 영역을 말합니다. 즉 동떨어진 두 영역을 가지는 나라는 생각하지 않습니다. 같은 이유로, 바다는 (하나의 색으로 칠해야 되니까) 동떨어진 여러 영역을 가지는 하나의 나라로 볼 수 있으므로, 역시 생각하지 않습니다.

만약 한 나라가 두 영역을 가지는 것을 고려하거나, 바다를 칠하는 걸 고려한다면 다음과 같이 4색문제의 간단한 반례를 찾을 수 있습니다.

3. 그래프로 생각하기

4색문제를 풀기 위해서는, 먼저 주어진 지도를 그래프로써 생각하는 단계가 필요합니다. 주어진 지도의 각각의 나라를 점vertex 들로 나타내고, 두 나라가 서로 이웃이면 두 점 사이에 선 edge하나를 긋습니다. 최종적으로 나온 결과가 바로 그래프 graph라고 불리는 물건입니다.

이와 같이 왼쪽의 네 개의 나라로 이루어진 지도를 오른쪽의 그래프로 나타낼 수 있습니다.

그런데, 왜 그래프로 바꾸어 생각하는 것일까요? 단순화 시켜 생각한다는 것은 수학문제의 기본 전략중 하나이긴 한데, 그 결과를 왼쪽과 살펴보면 큰 다른점이 없습니다. 오른쪽의 결과물도 결국 선과 지역을 가지죠. 선과 지역이 가리키는 대상이 다르지만. 그렇다면 아래처럼

이렇게 지도를 주물러서 단순화해도 되는 거 아닌가 하는 생각이 듭니다.

지도를 그래프로 왜 바꿀까요? 그것은 지도위에 존재하는 오브젝트가 가지고 있는 의미를 명확히 표현하기 위해서입니다. 우리가 중요하게 여기는 것은, 지도의 지리학적 모양이나 나라의 크기가 아니라, 각 나라들 그 자체와 그 나라들이 어떤 이웃들과 마주하느냐는 것이죠.

즉 ‘나라’, 그리고 ‘나라사이의 관계’ 만 알면 됩니다. 지도에서 나라라는 건 선이 둘러싸고 있는 영역이고, 나라사이의 관계는 그 선들의 좌우를 통해서 나타납니다. 그러나 그래프에서 나라는 점, 나라사이의 관계는 선으로 매우 명확한 오브젝트로 나타납니다. 그래서 그래프를 사용하는 것이지요.

5. 증명을 시작하는 방법

아주 간단한 예부터 확인해 봅시다.

문1 : 제곱해서 짝수가 되는 수는 반드시 짝수임을 증명하여라.

증명 : 제곱해서 짝수가 되는 수가 반드시 짝수일 필요는 없다고 해보자.

즉, 어떤 홀수 p가 존재하여, 이 수는 제곱하면 짝수가 된다.

그런데, p는 홀수이므로, 이를 제곱한 것은 홀수이다.

(왜냐하면 p는 홀수이므로, 어떤 정수 q가 존재하여, p = 2q+1로 나타낼 수 있는데,

그러면 p^2 = (2q+1)^2 = 4q^2+4q+1 = 2(2q^2+2q)+1 이므로, p의 제곱도 홀수이다. )

즉 p의 제곱은 짝수이면서 홀수여야 한다. 이는 모순이다.

따라서 처음의 가정 – 제곱해서 짝수가 되는 수 중에 짝수가 아닌 것도 있다 – 는 틀렸다.

따라서 제곱해서 짝수가 되는 수는 반드시 짝수이다. ///

쉽게 풀 수 있는 문제를 조금 오버해서 풀기는 했지만.. 어쨌든 이와같은 과정으로 증명하는 것을 귀류법이라고 합니다. 증명해야 하는 명제를 거짓이라 가정하고 논리전개를 한 다음에, 모순을 발견하는 것이죠. 논리전게 과정에서 틀린게 없다면, 틀린건 분명 가정 – 명제가 틀렸다는 가정 – 일 것입니다. 즉 명제가 틀린게 아니다 – 명제가 참이다 라는 것이죠.

다음은 제곱해서 2가 되는 수 중 양수 (루트2) 가 무리수임을 증명하는 과정입니다. 귀류법을 이용한 유명한 증명이죠.

문 : 루트2 가 무리수임을 증명하여라.

증명 : 루트2가 무리수가 아니라고 가정하자. 그러면 루트2는 유리수이다.

루트2가 유리수이므로, 유리수의 정의에 의하여, 어떤 서로소인 두 정수 p,q가 존재하여, 루트2 = p/q이다.

양변을 제곱하여 정리하면 2q^2 = p^2 을 얻을 수 있다.

p^2= 2q^2 라는 것은 p의 제곱이 짝수임을 의미한다. 그런데 제곱하여 짝수가 되는 수는 짝수밖에 없다. 따라서 p는 짝수이다.

따라서 어떤 정수 r이 존재하여, p = 2r이다. 이를 원래 식에 넣어보면, 4r^2 = 2q^2 이 된다.

양변을 2로 나누면, q^2 = 2r^2이 되어, q의 제곱은 짝수이고, q도 짝수가 된다.

이제 p와 q가 모두 짝수임을 알았다. 그런데 앞에서 p,q는 서로소라고 하였으므로, 이는 불가능하다.(모순!)

따라서 루트2는 무리수이다./// (S.Guri 님 오류수정 (2015-12-21 20:42:33))

우리는 4색문제를 귀류법을 통해서 증명할 것입니다. 즉.. 증명의 첫 줄은 이제 알았죠.

“ 4색문제가 거짓이라고 가정하자. 즉, 어떤 지도가 존재하여, 다섯 가지 이상의 색이 있어야만 칠할 수 있다. ”

그리고 증명의 마지막 줄도 이제 알았습니다.

.......이건 모순이다. 따라서 4색문제는 참이다.///

그럼 이제, 처음의 가정 – 다섯 가지 이상의 색이 있어야만 칠할 수 있는 지도(반례)가 있다 – 는 사실을 바탕으로 논리전개를 해서, 모순을 찾아내면 되는 것이죠.

오늘은 여기까지.