Tower of Hanoi

 

하노이(베트남의 도시)탑에 관한 문제의 고안자로 Lucas (프랑스인, 1842년) 라는 수학자가 알려져 있다. 1883년 Claus 라는 이름아래 이 하노이 탑 문제가 처음 나타났다. 가만히 살펴보면, Claus 라는 이름은 Lucas 라는 이름의 철자를 뒤바꿔 놓은 것임을 알 수 있다. 그가 쓴 수학게임에 관한 책 Récréations mathématiques (1882-94) 은 고전이 되어 있다.

전설의 내용

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

위의 경우는 원판의 개수가 2이다. 이 그림에서 보면은 최소한 3번 이동하면, 다른 원판으로 옮겨짐을 알 수가 있다. 그리고, 원판의 개수가 3이면, 최소이동 수는 7번이 됨을 알 수가 있다.

다시 정리하면, 원판의 개수를 n 이라 하고, 최소이동수를 M 이라 하면, n = 2 일때 M = ,   n = 3 일때 M = 이러한 식으로부터 추측을 하면, 64 개의 원판을 옮기는 데는 번이라는 것을 알 수가 있다.

전설에서처럼 64 개를 옮길 때, 한 번 옮기는 시간을 1초 걸린다고 가정 하면 64 개를 옮기는 데는 초가 걸린다는 것을 알 수 있고, 이를 년으로 환산하면, 대략 5833 억년 정도라고 한다.

태양과 지구에 관한 아래의 정보는 아래와 같다.

태양은 46억년 동안 활동해온 것으로 보이며 50억년은 더 태울 연료가 남아있다. 말기의 태양은 헬륨을 더욱 무거운 원소로 융합하는 반응이 일어나고 부풀어 오르는데, 지구를 삼킬 정도까지 극도로 커진다. 그 후 10억년은 적색거성(red giant)으로 생활하며, 이내 갑자기 수축하여 백색왜성(white dwarf) 이 된다 -- 우리의 태양과 같은 별의 종말은 이와 같다. 완전히 식으려면 아마 1조년 정도의 시간이 걸릴 것이다

따라서, 50억년 후에 태양이 적색거성이 되면, 지구가 생명체가 될 수 없는 상태가 되므로 종말이라고 볼 수 있고, 하노이 탑을 옮기는 데, 5833억년 정도는 걸리므로 그 안에 모든 지구의 모든 것이 끝난다는 것은 과학적으로 타당성이 있다.

자 그러면, 이를 수학적으로 정리를 해보자.

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

곧, n개의 원판을 이동하는 방법을 다음과 같다.

{A→B로 (n-1)개 이동} + {A→C로 1개 이동} + {B→C로 (n-1)개 이동}

이것을 식으로 나타내면, 이 식은 고등학교 2학년이상 수준이면, 일 반항을 구할 수 있다.

위의 식에서, 일반항 이라고 하면, 이 됨을 알 수 있다.

term :

하노이탑 (Tower of Hanoi)    수학 (Mathematics)    인공지능 (Artificial Intelligence)

site :

Hanoi Tower : 전북대 박순철 교수님 동영상

하노이 탑 속의 수학 원리 : 인터넷 스쿨 : 6 개의 원판을 옮기는 경우의 applet demo

Tower of Hanoi     

Tower of Hanoi : Java Puzzle : Disc(원판) 를 12 개까지 조절하고 Speed 를 조절하며 움직임(Move)의 수를 셀 수 있다.

video :

거듭제곱의 위력 : 수학으로 푸는 세상의 비밀 - YTN 사이언스 : 박경미 홍익대교수, 2014/02/12

 

... 위의 동영상 15분부터 하노이탑 설명합니다. ...