달력

2

« 2020/2 »

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
2007. 7. 9. 00:06

Four-Colorist Math2007. 7. 9. 00:06

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

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

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

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

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

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

Four Colors Suffice

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

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

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

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

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

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

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

사용자 삽입 이미지

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

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

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

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

'Math' 카테고리의 다른 글

Advisor of Fields medalists  (6) 2007.07.12
조선일보 기자의 산수 실력  (5) 2007.07.11
Four-Colorist  (3) 2007.07.09
안습의 trisector  (9) 2007.07.02
abc conjecture  (3) 2007.06.26
Riemann hypothesis disproved?  (2) 2007.06.12
Posted by puzzlist

댓글을 달아 주세요

  1. 상일 2007.07.09 06:00  댓글주소  수정/삭제  댓글쓰기

    조금 첨언하자면, Appel과 Haken의 증명에 대해서는 100% 정확하지는 않을수도 있다고 생각하는 사람들도 있긴 합니다. 하지만 그 이후에 Robertson, Sanders, Seymour, Thomas가 또한번 증명을 했지요. 물론 이것도 컴퓨터를 이용하였지만, 따지는 경우 수가 훨씬 줄었습니다.
    http://www.math.gatech.edu/~thomas/FC/fourcolor.html
    여기를 참조하세요. 어쨌든 이제는 4CT 정리 자체는 정리로 인정받고 있습니다.

  2. 서상현 2007.07.09 10:00  댓글주소  수정/삭제  댓글쓰기

    위에 링크된 경우의 수를 줄인 증명 외에도, 방향을 완전 반대로 가서 컴퓨터만으로 검증 가능한 formal proof도 작성되었습니다.

    Georges Gonthier가 프랑스 INRIA에서 개발한 Coq proof assistant로 작성한 formal proof:
    http://research.microsoft.com/~gonthier/

  3. 하얀까마귀 2007.07.09 20:23  댓글주소  수정/삭제  댓글쓰기

    요즘 틈틈이 "어떻게 해야 사람 손으로 풀기 어렵게 지도를 만들수 있을까" 궁리중인데, 생각보다 재미있네요. 물론 '나라' 갯수는 가능한 한 줄이면서...