하노이 탑(tower of hanoi)

하노이 탑(The Tower of Hanoi puzzle)은 1883년 프랑스의 수학자 루카스(Edouard Lucas)에 의해 개발되었다. 하노이(베트남의 도시)탑에 관한 문제의 고안자로 Lucas (프랑스인, 1842년) 라는 수학자가 알려져 있다. 1883년 Claus 라는 이름아래 이 하노이 탑 문제가 처음 나타났다.

가만히 살펴보면, Claus 라는 이름은 Lucas 라는 이름의 철자를 뒤바꿔 놓은 것임을 알 수 있다. 그가 쓴 수학게임에 관한 책 Récréations mathématiques (1882-94) 은 고전이 되어 있다.

베나레스에는 세계의 중심이 있고, 그 곳에는 아주 큰 사원이 있다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3 개가 있다. 그 중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64 장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮겨 빈 다이아몬드 막대 중 어느 곳으로 모두 옮겨 놓도록 명령하였다.

원판은 한 번에 한 개씩 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려 놓을 수 없다. 64개의 원판이 본래의 자리를 떠나 다른 한 막대로 모두 옮겨졌을 때에는 탑과 사원, 승려들은 모두 먼지가 되어 사라지면서 세상의 종말이 온다.

 

풀이1 ::::::::: 계차수열을 써서 구하기

n을 원판의 개수라고 하고 이 때 이동횟수를 `a_{n}`라고 하자.
하나하나 세어보면
`a_{1}=1`, `a_{2}=3`, `a_{3}=7`, `a_{4}=15`, `a_{5}=31`
계차수열을 `b_{n}=a_{n+1}-a_{n}`이라하면
`b_{1}=2`, `b_{2}=4`, `b_{3}=8`, `b_{4}=16`이다.
일반항은 `b_n =2^n` 이다.
$$a_{n}=a_{1}+ \sum_{k=1}^{n-1} b_{k}$$에서
$$a_{n}=1+ \sum_{k=1}^{n-1} 2^{k}=1+ \frac{2(2^{n-1}-1)}{2-1}$$
그러므로 `a_{n}=2^{n}-1`이다.

풀이2 ::::::::: 점화식을 써서 구하기

n을 원판의 개수라고 하고 이 때 이동횟수를 `a_{n}`라고 하자.
n개의 원판을 옮기려면 위쪽에 있는 (n-1)개의 원판을 모두 다른 막대로 옮긴 후에 맨 아래 원판을 빈 막대로 옮기고, 다시 그 위에 (n-1)개의 원판을 옮겨 놓으면 된다.

곧, n개의 원판을 이동하는 방법은 다음과 같다.
{A→B로 (n-1)개 이동}+{A→C로 1개 이동}+{B→C로 (n-1)개 이동}
이것을 식으로 나타내면
`a_{n}=a_{n-1} +1+ a_{n-1}`
이 수열을 귀납적으로 정의해보면
`a_{1}=1`, `a_{n+1}=2a_{n} + 1`이다.
`a_{n+1}+1=2(a_{n} + 1)`
`b_{n}=a_{n}+1`이라고 하면
`b_{n}`은 첫째항은 `b_{1}=a_{1}+1=2`이고 공비가 2인 등비수열이다.
따라서 `b_{n}=2^n`
그러므로 일반항은 `a_{n}=2^{n} -1`이다.

• 전설처럼 64개를 옮길 때 한 번 옮기는 시간을 1초 걸린다고 하면 얼마나 걸리나?
  

64개를 옮기는 데는 `2^{64} -1`초가 걸린다. 이를 햇수로 따져보면 대략 5833억 년 쯤 된다.
세상이 끝나지 않을까 걱정하진 맙시다.