[퀴즈로 푸는 수학] (5) 경계 구별하기

세계 지도에서 서로 다른 나라의 경계를 구분하기 위해서는 최소한 몇 가지 색이 필요할까요?실제로 여러 가지 영역을 정하여 과연 몇 가지 색으로 각 영역의 경계를 구분할 수 있는지 알아봅시다.

규칙은 다음의 2가지입니다.

(1)같은 경계선을 갖는 두 개의 영역은 서로 다른 색이어야 합니다.

(2)오직 한 점에서 만나는 영역은 같은 색으로 칠할 수 있습니다.

(문제1)

이 규칙에 따라 다음 사각형 안에 있는 영역을 색칠하시오.(단, 가능한 가장 적은 수의 색을 이용해야 합니다.)

(문제2)

이번에는 직선으로 이루어진 영역입니다. 규칙은 위와 같습니다. 경계를 구분할 수 있는 최소한의 색을 이용하여 칠하시오,

(해답)

(1)왼쪽 사각형은 3가지, 오른쪽 사각형은 4가지의 색으로 칠할 수 있습니다. 직접 색칠해서 확인해 보시오.

(2)이렇게 복잡해 보이는 직선 지도도 단 2가지의 색으로 경계를 구분할 수 있습니다.

실제로 모든 백지도들에 칠해보면 4가지 색깔만으로도 충분히 경계를 구별할 수 있습니다. 하지만, 이것을 수학적으로 증명하기란 그리 쉽지 않았다고 합니다.1963년에 오르(Ore)라는 수학자에 의해 5가지의 색깔로 지도의 경계를 구분할 수 있다는 것을 수학적으로 증명해 보였습니다.

그 후 1976년 6월 미국의 일리노이주 대학의 두 수학자에 의해 4가지 색으로 모두 구별할 수 있다는 것이 증명되었습니다. 그러나, 이 문제를 증명하는 데 컴퓨터로 처리하는 데만 1200시간이 걸렸다고 합니다. 사실상 이 문제의 증명은 컴퓨터의 사용이 없었다면 불가능한 일이었습니다.

서울금동초등학교 교사 임창균