수학 애호가들이 미로를 푸는 법

트위터 계정 mathlava에서는 비교적 간단한 물음에 수학적인 원리가 숨어있으면서도 기상천외한 방법으로 답하는 답안을 자주 모집하곤 한다. 이러한 답안들을 모아 책도 발간했는데 최근 한국어판으로도 정발되었다. 가장 유명한 아웃풋으로는 아래와 같은 원의 삼등분 문제가 있다.

최우수상에 빛나는 육망성의 위엄

최근에는 미로를 푸는 방법의 다양한 해법을 모집했는데, 주제가 주제이다보니 원리보다는 시각화에 초점을 맞춘 경우가 많았다.

주제를 올리기 전에 올라온 트윗인데, 사실 벼락이 치는 과정의 모델링으로도 볼 수 있다. 실제로 벼락은 전하들이 저항이 매우 높은 공기에서 저항이 낮은 쪽을 탐색하다가 지면에 닿는 순간 그 경로가 회로로 성립해 전류가 흐르는 것임을 감안하면…

시작하는 곳을 위로 두고 유체를 채우다보면 언젠가 끝나는 부분으로 넘치게 된다는 기존 아이디어.

기체 분자 시뮬레이션을 이용한 역시 기존의 미로 풀이.

<모야시몬>에서도 소개된 적 있는 점균의 미로 찾기. 시작 부분에 점균을 두고 끝 부분에 영양분을 두면 탐색을 진행하다가 영양분을 찾으면 두 지점을 연결하는 경로로 점균이 집중하게 된다.

모든 길을 고무로 채우고 두 끝점을 잡고 잡아당길 때 생기는 길이 곧 해답 경로가 된다는 아이디어.

최우수상을 받은 답안으로 3면으로 막힌 곳을 하나씩 없애나가는 방법인데 솔직히 너무 직설적이고 twist가 없는 것이 아닌가 싶음…

가장 마음에 들었던 답안은 이쪽. 각 칸에 해당하는 변수 x_{ij}를 마련하고 스타트 지점은 0, 끝 지점은 1, 데드엔드 칸들은 0을 미리 부여한다. 그 외의 칸들은 인접한 칸들과 자기 자신에 해당되는 x의 평균을 y로 정의하면 이 칸들에 대해 위 그림 좌하단과 같은 선형 방정식을 만들 수 있고, 그 행렬 M의 고유벡터 중 고윳값이 1인 것을 잡아 v라고 한다. 그러면 스타트 지점부터 시작해 인접한 칸들 중 v_{ij}의 값이 증가하는 쪽으로 이동하면 그게 최단경로가 된다고 한다. 아마 각 칸에서 스테이하거나 인접한 두 칸 중 하나로 1/3의 확률로 이동하는 Markov process의 stationary distribution을 생각하면 될 듯.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중