d라이브러리









아마추어 수학자의 활약! 평면 채색수 문제

그리스의 수학자 에우클레이데스(유클리드)가 ‘기하학 원론’이라는 평면 기하 교과서를 쓴 지 1700여 년이 지났습니다. 하지만 아직도 미해결인 평면 기하 문제가 많습니다. 이번 호에 소개할 문제 역시 그중 하나입니다. 1950년 대학에 갓 입학한 새내기가 만든 문제로, 최근 영국의 생물학자인 아마추어 수학자가 이 문제에 관해 의미 있는 결과를 발표했습니다.

 

 

평면의 각 점에 색을 칠하는데, 거리가 정확히 1 떨어진 점은 다른 색이 되게 칠하려고 합니다. 색이 최소 몇 개 필요할까요?

 

이 같은 규칙으로 칠할 때 필요한 최소 색의 수를 ‘평면 채색수(χ)’라고 합시다. 이 값을 구하는 문제는 사실 누가 처음으로 냈는지가 기록마다 달라 혼란이 있었습니다. 1990년대 미국 수학자 알레산더 소이퍼 교수가 이 문제에 관한 글을 쓴 사람을 일일이 연락해 추적한 끝에 출제자를 밝혀냈지요.

 

바로 1950년 당시 만 18세로 미국 시카고대학교 수학과에 갓 입학한 에드워드 넬슨이었습니다. 뛰어난 학생이었던 넬슨은 3년만에 석사, 2년 만에 박사 학위를 받고, 1959년에 미국 프린스턴대학교 수학과 교수가 됩니다.

 

한편 평면 채색수는 항상 3 이상입니다. 어떻게 알 수 있을까요? 한 변의 길이가 1인 정삼각형을 그려봅시다. 그러면 정삼각형의 세 꼭짓점은 서로 다른 색이 돼야 하므로 3색 이상이 필요합니다.

 

4 이상일 수는 없을까요? 넬슨은 곧바로 이게 참이라는 걸 알아냅니다. 정삼각형 4개를 겹쳐서 아래와 같은 그림을 만듭시다. 이때 점 D와 점 G의 거리는 1입니다. 그러면 각 변은 모두 길이가 1인 선분입니다. 이제 χ≥4임을 증명하기 위해 이 그림에 있는 점을 모두 3색으로 칠할 수 있다고 가정 합시다.

 

 

△ABC는 한 변의 길이가 1인 정삼각형이므로, 각 꼭짓점의 색은 다릅니다. 마찬가지로 △BCD의 모든 꼭짓점도 색이 다른데요, 칠할 수 있는 색이 3개 밖에 없다고 가정했기 때문에 점 A와 점 D의 색은 같아야 합니다.

 

같은 방법으로 △AEF와 △EFG의 꼭짓점을 칠합니다. 정삼각형을 이루고 있는 꼭짓점의 색은 모두 다르고 3색으로만 칠하다 보니 어쩔 수 없이 점 D와 점 G의 색이 같아집니다. 그런데 앞서서 두 점 사이의 거리는 1이라고 했기 때문에 모순이 생기고 맙니다. 결국 4색은 돼야 하지요.

 

 

에르되시도 인정한 좋은 문제


이제까지 색의 수가 너무 적으면 절대 칠할 수 없다는 부정적인 결과만 소개했습니다. 반대로 색이 충분히 많으면 무조건 된다는 긍정적인 결과에는 어떤 것이 있었을까요?

 

 

넬슨의 대학 선배인 미국 수학자 존 이즈벨은 넬슨이 χ≥4만 증명했다는 소리를 듣고, 궁리해 χ≤7임을 보였습니다. 사실 7색으로 칠하는 방법에는 여러 가지가 있습니다. 그중 가장 많이 알려진 건 정육각형으로 평면을 가득 채우는 방법에서 착안한 겁니다.

 

정육각형의 한 변의 길이를 잘 정해 위 그림처럼 같은 색으로 된 두 정육각형은 서로 거리가 1보다 크게 하고, 정육각형 안에는 거리가 1 떨어진 두 점이 없도록 만들면 됩니다.

 

그렇다면 χ는 4, 5, 6, 7 중 얼마일까요? 정말 많은 수학자와 공동연구하며 여러 문제를 섭렵했던 헝가리 수학자 에르되시 팔도 이 문제에 도전했습니다. 1992년 강연 도중 이 문제를 언급하면서, 아주 좋은 문제고 내가 만든 문제라면 250달러 정도를 상금으로 걸었을 것이라고 말하기도 했습니다. 에르되시는 자기가 낸 문제마다 난이도에 따라 1달러부터 5000달러까지 상금을 건 것으로 유명하죠.

 

에르되시는 네덜란드 수학자 니콜라스 더브라윈과 함께 만일 χ>k라면 k개 색으로 칠할 수 없는 유한개의 점이 반드시 있다는 것을 증명했습니다. 무한히 많은 점 때문에 어려운 문제로 보이지만, 덕분에 평면에서 유한개의 점을 뽑았을 때 몇 가지 색으로 칠할 수 있냐는 유한에 관한 문제로 바꿔서 생각할 수 있게 됐습니다.

 

 

 

1000년 살 수 있다는 생물학자가 문제 해결


그 뒤로 얼마 전까지 이 문제에 관한 진척이 별로 없었습니다. 그러던 2018년 4월 8일, χ≥5라는 것을 증명한 논문이 인터넷에 올라왔습니다. 이 연구를 한 사람은 수학자가 아니라 ‘인간은 1000세까지 살 수 있다’는 다소 과격한 주장을 하는 영국 생물학자인 오브리 드 그레이입니다.

 

그레이 박사는 4색으로 칠할 수 없는 점 1000여 개를 평면에서 잘 찾아냈습니다. 아까 χ≥4를 증명하기 위해서 3색으로 칠할 수 없는 점 7개를 소개했는데요, χ≥5를 보이기 위해 훨씬 더 많은 점을 사용한 것이지요.

 

저는 수학자가 한 연구도 아니고 해서 이 논문에 관심을 갖지 않았습니다. 그런데 며칠 뒤 컴퓨터로 연구를 검증했다는 학자들이 여럿 나타났고, 결과가 참이라는 것이 밝혀졌습니다.

 

 

마레인 횔러 박사가 찾은 4색으로 칠할 수 없는 633개 점. 수학자는 평면 채색수가 4일 수는 없다는 걸 보이기 위해 필요한 최소 점의 개수를 구하는 문제를 폴리매스 프로젝트 16번 문제로 등록하고 함께 답을 찾고 있다.

 

 

 

보통 수학 논문을 검증하는 데 꽤나 긴 시간이 걸립니다. 그런데 이 문제의 경우 오래 걸리지 않았습니다. 논문에서 이야기하는 점을 어떻게 뽑은 것인지만 알면 컴퓨터를 써서 바로 확인할 수 있기 때문입니다. 그레이 박사의 논문에는 1581개의 점을 뽑아내는 방법이 나와 있고, 왜 4가지 색으로 칠할 수 없는지 알아낸 방법이 나옵니다.

 

한편 4월 14일부터 폴리매스 프로젝트를 통해 여러 사람이 4색으로 칠할 수 없는 점의 최소 개수를 찾고 있습니다. 그레이 박사가 만든 그래프를 조금 더 간단한 것으로 계속 바꿔나가면서 계산하고 있는데, 현재 최고 기록은 5월 6일 미국 텍사스대학교 오스틴캠퍼스 소속의 마레인 횔러 박사가 공개한 633개입니다.

 

χ는 과연 얼마일까요? 5, 6, 7? 과연 또 누가 이 문제로 사람들을 깜짝 놀라게 할지 궁금합니다. 누구든 도전하면 아무도 생각하지 못한 아이디어로 χ<7이나 χ>5를 증명할 수 있지 않을까요?

 

 

엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재는 KAIST에서 강의와 연구를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐습니다.

2018년 06호 수학동아 정보

  • 엄상일(KAIST 수리과학과 교수) 진행 조가현 기자(gahyun@donga.com)
  • 기타

    [일러스트] 오승만
  • 참고자료

    오브리 드 그레이 ‘The chromatic number of the plane is at least 5’, 이블린 램 ‘Quanta Magaznie : Decades-Old Graph Problem Yields to Amateur Mathematician’, 폴리매스 사이트(http://michaelnielsen.org/polymath1/) ‘Hadwiger-Nelson problem’, 알렉산더 소이퍼 ‘The mathematical coloring book. New York’, 알렉산더 소이퍼 ‘The Hadwiger-Nelson problem’

🎓️ 진로 추천

  • 수학
  • 컴퓨터공학
  • 생명과학·생명공학
이 기사를 읽은 분이 본
다른 인기기사는?