하노이의 탑

n단짜리 하노이의 탑의 m번째 상태를 알고 싶다고 하자. 이때 처음으로 더듬어볼 화살표는 가장 바깥쪽에 있는 가장 큰 반원(원판 n)을 가로지르는 화살표 1(→n)2이다. 그 화살표가 가리키는 가로축의 검은 점에는 번호 2^n-1이 붙어 있을 것이다. 이것은 다음 사실을 의미한다.

우선, m<2^n-1이라면 제일 큰 원판 n은 아직 기둥1에 있고, 원판 n을 제외하고 생각한 n-1단짜리 하노이의 탑을 기둥1에서 기둥3으로 대피시키는 작업을 실행중이다. m=2^n-1이라면 마침 제일 큰 원판 n을 기둥1에서 기둥 로 이동시키려는 참으로, 그것이 가능하도록 원판 n 위에 쌓여 있던 n-1단짜리 하노이의 탑이 이제 막 기둥3으로 모두 대피를 마친 상태이다. 즉 이 경우에는 각가의 주어진 시점에서 모든 원판의 위치를 알 수 있다. 마지막으로 m>2^n-1 이라면 제일 큰 원판 n은 기둥2로 이동을 마친 상태이고 기둥 3에 대피해 있던 원판들 (n-1단짜리 하노이의 탑 원판들)이 이동하고 있는 중이다.

이것으로 원판 n의 위치가 확정됐다. m=2^n-1의 경우에는 다른 원판의 위치를 확정하기 위해 좀 더 살펴볼 필요가 있다.

m<2^n-1의 경우는. m번째 움직임에 대응하는 검은 점은 한가운데보다도 왼쪽에 위치하고 있으므로, 두 번째 큰 반원(원판 n-1에 대응) 중 왼편 속에 표시된다. 그 반원은 n-1단짜리 하노이의 탑을 기둥1에서 기둥33으로 대피시키는 작업을 꿰고 있으므로, 앞에서와 마찬가지로 그 반원을 자르는 화살표에 쓰인 번호를 보면 원판 n-1이 어디에 있는지 알 수 있다.

한편 m>2^n-1의 경우에는 대피해둔 n-1단짜리 하노이의 탑을 다시 기둥3에서 기둥2로 이동시키고 있는 중이다. 그 상황은 오른쪽의 두 번째로 큰 반원을 자르고 있는 화살표가 나타내고 있으며 거기 쓰인 번호를 보면 원판 n-1이 지금 어디에 있는지 판단할 수 있다. 일단 오른쪽 반원에 들어가 버리면 밖으로 나오는 일은 없기 때문에, 원판을 움직인 횟수를 그 반원의 첫 위치(왼쪽 끝)을 기점으로 하여 다시 세서 그 뒤를 계속 고찰하는 편이 편리하다. 즉 그 오른쪽 반원에 대응하는 이동을 시작하기까지 이미 왼쪽 반원에서 2^n-1번 l동을 하고 있으므로, 그 기점에서 몇 번 옮겼나 하는 횟수는 m-2^n-1이다.

왼쪽이든 오른쪽이든, 더욱 반원 내부로 진입하면서 위와 같은 고찰을 반복하면 번호가 작은 편의 위치도 확정돼간다는 것을 알 수 있을 것이다. 그리고 화살표가 직접 검은 점을 가리키고 있는 상태가 된 시점에서 모든 원판의 위치가 확정된다. 그렇게 될 때까지 왼쪽으로 갔다가 오른쪽으로 갔다가 하는 것을 반복하는데, 오른쪽 반원으로 진입할 때마다 m의 값은 상대적인 것으로 치환되어 작아져간다. 최종적으로 그 값이 2의 거듭제곱 형태로 됐을 때, 화살표가 검은 점을 직접 가리키는 상태로 되는 것이다.

결국은 단수가 많아지면 해명도가 복잡해지기는 해도 반복되는 것은 늘 같다. 그것을 반원의 존재를 무시하고 써 내려가면, 다음과 같이 정리된다.(n단의 하노이의 탑을 푸는 데 있어) 1의 초기 값을 n으로 하고, l을 한 개 씩 작게 해나가면서 이것을 반복해가면 큰 원판에서부터 차례로 그 위치가 특정화돼간다.

전체 주어진 횟수를 m으로 하고, 원판 l+1에서 원판 n까지의 위치는 이미 확정돼 있다고 친다.

● m= 2^l-1의 경우

원판 l이 기둥i에서 기둥 j로 움직인다.

원판 1에서 원판 l-1까지는 기둥 k에 있다.

모두 결착.

● m<2^l-1의 경우

원판1은 기둥i에 있다.

원판1에서 원판l-1까지를 기둥i에서 기둥k로 이동중.

이동해갈 곳 j를 k로 바꾸어놓고 l-1단짜리 하노이의 탑을 i에서 k로 이동한다고 생각하라.

● m>2^l-1의 경우

원판 l은 기둥j에 있다.

원판1에서 원판l-1까지를 기둥k에서 기둥j로 이동중.

m을 m-2^l-1로 바꿔놓고, l-1단짜리 하노이의 탑을 k에서 j로 이동한다고 생각하라.

p.s 공식으로 쓴건 모르겠다.