63세 전직 경비원 Road Coloring Problem 풀다

글쓴이: imyejin / 작성시간: 금, 2008/03/21 - 3:03오후

러시아 출신 유태인 수학자인데 돈이 없어서 이스라엘 가서 경비원 했다는군요.
1년만에 8쪽짜리 해법으로 증명했다고 합니다. 무슨 이런 돌하나스러운 일이 ...

영어 기사 http://ap.google.com/article/ALeqM5g2lh1_jNDbrmhNoMlwkZTfLeCw8gD8VHBPIO0
우리말 기사 http://news.empas.com/issue/show.tsp/cp_yt/876/20080321n08721/

저도 기사 보고 문제는 처음 알았는데 아래 위키피디아 페이지에 가면 설명이 있고
http://en.wikipedia.org/wiki/Road_Coloring_Conjecture
아직 문제 자체가 정확히 무슨 뜻인지 이해가 안갑니다.

이 문제에 대해 혹시 잘 알고 계시는 분이 계시면 설명해 주시면 감사하겠습니다.

Forums:

뉴스, 새소식

문제는 어떤 사람의

글쓴이: select99 / 작성시간: 금, 2008/03/21 - 6:15오후

문제는 어떤 사람의 현재 위치와 상관없이 목적지로 안내할 수 있는 하나의 보편적 지도를 그려낼 수 있다고 가정한다.
 
이 문제의 전제는 지도상에 일정한 수의 도시가 있고 각 도시에서 나오기만 할 수 있는 도로가 2개씩 있으며 도로들은 출발점으로 되돌아가거나 다른 도시로 향할 수 있는데, 각 도시에서 출발하는 도로들을 다른 두가지 색깔로 구분한다는 것이다.
 
이때 도로를 구분하는 색깔들을 나열함으로써 어떤 도시에서든 다른 도시로 가는 길을 설명할 수 있다는게 이 문제의 주된 내용이다.

제가 영어 실력이 없어 그냥 이미지와 뉴스내용을 보니..
"도시로 가는길을 설명할수 있다"는게 이문제의 주된네용이라네요..

그렇다면. 특정한곳으로 가는 그 말.. 을 찾으면되는건가? 아니면 왜그런지를 설명하면되는건가..?

어쨋든..
2색경로에서 반드시 주변의 두곳과 연결(출구) 가있으므로 이곳이 못갈곳이 없다면 반드시 원하는곳으로 가게된다. 그렇다면 주변을 맴도는 색의경로가 유니크한경우 가능하다.

즉, 특정지점의 주변을 맴도는 색경로가 유니크한경우(색경로의배수조차맴도는경로가 없는) 그색경로를 반복함으로써 어디에있든 특정지점에 도달하게된다. 즉, 유니크한 맴도는 색경로를 찾으면된다.

이미지의 맨위지점은..블루래드블루가 맴도는 색경로이므로 해답은 블루래드블루의 반복이다.

라고 말하면....

프로램가능 할듯한데.. 각지점의 맴도는3색경로,4색경로... (와 배수경로)가 다른지점의 맴도는경로와 겹치지 않은지..판단해보면..