본문 바로가기

수학의 난제3

4색 문제(four color problem) 1852년 10월, 영국 런던에 있는 유니버시티 대학(University College)의 대학원생 프렌시스 구드리에(Francis Guthrie)는 영국 지도를 색칠해 나가다가 '인접한 구획들이 같은 색으로 칠해지는 경우가 없게 하려면 최소한 몇 가지의 색이 필요할까?'라는 의문을 갖게 되었다. 결국 영국의 지도에 있는 지역들을 구별하여 색칠하는 데는 4가지 색이면 충분하다는 사실을 알게 되었다. 그는 임의의 구획으로 나누어져 있는 지도를 칠할 때 4가지 색이면 대부분 되는 것 같았지만 확신을 가질 수는 없었다. 다섯 가지 이상의 색을 사용해야 조건에 맞게 그릴 수 있는 지도가 존재할까, 아니면 네 가지 색이면 어떤 지도에서도 인접한 구획들이 다른 색으로 칠해질 수 있음을 증명할 수 있을까? 구드리에는.. 2015. 5. 13.
우박 수열 - 콜라츠 추측 독일의 수학자인 콜라츠(Collatz, L. ; 1910~1990)는 1937년에 다음과 같이 정의되는 자연수의 수열을 소개하였다. ❶ 이 홀수이면, ❷ 이 짝수이면, 이와 같은 수열이 어떤 성질을 갖는지 알아보자. 만약 이면 , , 이다.따라서 이 1, 2, 4인 경우에는 그 이후에 4, 2, 1이 반복되어 나타나게 된다. 예를 들면 다음과 같다. 이면 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … 이면 5, 16, 8, 4, 2, 1, 4, 2, 1, … 이면 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … 아래의 그래프는 일 때의 수열 을 그래프로 나타낸 것이다. 이 그래프는 마치 롤러코스터처럼 상승과 하강을 반복하다가 4, 2, 1이 반복되면서 안정된다 .. 2014. 12. 12.
해밀턴의 세계 일주 게임 19세기 영국의 수학자 해밀턴은 그래프와 관련된 여러 가지 재미있는 문제를 제기하였는데 그 중에는 아직까지 완전히 해결되지 않은 문제도 있다. '세계 일주 게임'은 그가 1857년에 소개한 것으로, 정십이면체의 20개의 각 꼭짓점에 세계의 유명한 도시의 이름을 붙인 후, 어느 한 도시를 출발하여 모서리를 따라 다른 도시를 모두 방문하고 처음 도시로 돌아오는 게임이다. 이때, 한 번 방문한 도시는 다시 방문하지 않는다. 해밀턴은 정십이면체를 평면그래프로 나타내어 이 문제를 다음 그림과 같이 해결하였다. 위의 게임에서와 같이 같은 길을 지나지 않고 주어진 그래프 상의 점을 모두 한 번씩 지나서 출발점으로 돌아올 수 있는 길을 '해밀턴 폐쇄로'라고 한다. 해밀턴 폐쇄로 문제는 '어떤 경우에 해밀턴 폐쇄로가 있.. 2014. 12. 5.