하노이 탑과 점화식

퍼즐의 시작

하노이 탑(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개일 때는 당연히 1번 옮기면 끝난다.

2개일 때는 아래 그림과 같이 3번 옮기면 된다.

이런 자연수와 관련된 문제는 당연히 수열로 생각해야 편하다.

$n$개일 때 옮겨야 하는 횟수를 $a_n$이라고 하자.

$$a_1 =1, \quad a_2=3$$

아래 그림은 $n=7$일 때를 나타낸다.

먼저 6개를 가운데로 옮기고 가장 큰 파란 원판을 옮긴 다음 다시 가운데 있는 6개 원판을 옮기면 된다. 

이를 식으로 나타내면 아래와 같다.

$$a_7=a_6+1+a_6$$

이 관계를 일반화하면 아래와 같다.

$$a_{n+1}=a_n+1+a_n$$

즉 하노이 탑 문제를 해결하는 수열은 아래와 같이 귀납적으로 정의할 수 있다.

$$a_1=1,\quad a_{n+1}=2a_n+1$$

일반항 구하기

$$1,\;\;3,\;\;7,\;\;15,\cdots$$

일반항 $a_n=2^n-1$로 예상할 수 있다.

수학적 귀납법으로 증명하기

1) $a_1=2^1-1=1$이므로 $n=1$일 때 성립

2) $n=k$일 때, $a_k=2^k -1$이라고 하면

$a_{k+1}=2a_k +1=2(2^k-1)+1=2^{k+1}-1$이므로 $n=k+1$일 때도 성립한다.

1)과 2)에 따라서 모든 자연수 $n$에 대하여 $a_n=2^n-1$이다.

또 다른 방법

$a_1=1$

$a_2=a_1+2$

$a_3=a_2+2^2$

$a_4=a_3+2^3$

$\vdots$

$a_{n-1}=a_{n-2}+2^{n-2}$

$a_n=a_{n-1}+2^{n-1}$

변변 더하면

$a_n=1+2+2^2+\cdots+2^{n-1}=2^n-1$

퍼즐의 완성

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

$2^{64}-1$초는 과연 몇 년일까 대충 계산해 보자.

1년은 $365\times24\times60\times60\approx2^{25}$초이다. 따라서 $\displaystyle{\frac{2^{64}-1}{2^{25}}\approx2^{39}=549,755,813,888}$년이나 걸린다. 대충 5497억 년이다. 아래 사이트에선 5880억 년이라고 하니 이쯤이면 세상의 종말을 걱정할 필요가 없다.

인공지능의 답변

너무 대충했나 싶어서 챗지피티에게 물었다. 확실히 빠르고 정확하다.^^

물음: $2^{64}$초는 몇 년인가?

대답: $2^{64}$초는

$$2^{64} = 18,446,744,073,709,551,616 \text{초}$$

입니다. 이를 1년을 약 365.2425일로 하여 환산하면

$$\frac{2^{64}}{60 \times 60 \times 24 \times 365.2425}\approx 584,554,049,254$$

이므로, 약 5,845억 5천만 년입니다.

비교해 보면:

• 지구의 나이: 약 45억 년
• 우주의 나이: 약 138억 년
• ($2^{64}$)초: 약 5,845억 년

즉, 우주의 현재 나이보다 약 42배 정도 긴 시간입니다.

 

 

하노이 타워 - 자바실험실

하노이 타워 - 자바실험실