1 유래
베트남의 수도 하노이에 있는 불교 사원에 전해지는 이야기.
여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 63개(혹은 64개)의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다.
이 원반들이 처음 있던 기둥에서 다른 기둥으로 모두 옮겨지면 세계가 멸망한다고 한다.
간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다'는 룰로 인하여 영겁의 세월에 걸친 노가다(...)를 창시했다. 위의 규칙을 따랐을 때 n개의 원반을 한쪽 기둥에서 다른쪽으로 옮기는데 걸리는 최소 횟수는 [math] 2^n - 1 [/math]번이다.
그 원리는 [math] n [/math]번째 원반을 한쪽기둥으로 옮기는 데 필요한 최소 횟수를 [math] a_n [/math]라고 하면 [math] (n+1) [/math]번째 원반을 옮기려면([math] a_{n+1} [/math]을 구하려면) [math] n [/math]번째 까지의 원반을 한쪽 기둥으로 옮기고([math] a_n [/math]를 더하고) [math] (n+1) [/math]번째 원반을 비어있는 기둥에 옮기고([math] 1 [/math]을 더하고) [math] n [/math]번째까지의 원반을 [math] (n+1) [/math]번째 원반 위로 옮기면([math] a_n [/math]를 다시 더하면)된다.
따라서 [math] a_{n+1}=2a_n+1 [/math]이고 이 관계식, 점화식에 의한 수열 [math] a_n [/math]의 일반항을 구해보면 [math] a_n=2^n - 1 [/math]가 나온다.[1]
63개의 원반을 완전히 옮기는 데 걸리는 횟수는 [math] 2^{63} - 1 [/math], 자그마치 9,223,372,036,854,775,807(922경 3372조 368억 5477만 5807)회에 달한다.이는 판을 한번 옮기는데 1초가 걸린다 해도 약 5833억 년이 걸리는 횟수이며지금까지의 우주의 나이(130~135억)년보다도 훨씬 길고 우주가 멸망할 수도 있는 시간이다. 바너드 별의 예상 수명(약 2조 5000억년)보다는 훨씬 짧긴 하지만 그래도 무지막지하게 긴 시간이다. 참고로 이의 절반은 128비트 오류가 일어나기 위해 필요한 시간이다. 멸망은 하긴 한다 64개라 한다면 18,446,744,073,709,551,615 대략 두배의 시간이 걸릴 것이다! 아이고 맙소사
그러나 만약 막대를 하나 더 추가해서 네 개로 만든다면, 방법에 따라 최소 18,433번만 옮기면 모두 옮길 수 있다!!! 이는 1초에 1개의 판을 옮긴다고 할 때 달랑 5시간 7분 13초 정도 걸리는 수준이다!!!
2 퍼즐 게임
흔히 하노이의 탑을 말하면 이쪽을 말한다. 1의 이야기에서 따와 3개의 기둥에 적당한 개수의 원반을 쌓아놓고 다른 쪽으로 옮기는 게임.
1에도 나와 있듯이 원반 개수가 늘어날수록 이동 횟수가 엄청나게 늘어나기 때문에 많아봐야 7, 8개 정도만 쓴다. 소모 시간으로 승부를 짓는 것이 보통. 이 정도면 초당 1번로 쳤을 때 2~4분 가량 걸리고, 실제로는 그것보다 덜 걸린다.
하지만 솔직히 창의력을 키워준다는 수학 학원이나 영재원에서 교재나 폼, 장식용으로만 쓰일 뿐 초딩이 지나면 버려지는 게 대부분. 해외엔 관련 대형 단체/대회가 있는지는 확인 바람.
프로그래밍 공부를 하는 사람들의 초반의 벽이 이것의 알고리즘을 구현하는 것.
알고리즘은 의외로 간단하다. 원반의 총 개수를 n이라 할 때 원반의 이동 회수는 위에서 언급한 대로 [math]2^n-1[/math]번이 되며, 각 회차를 x라 할 때(1부터 [math]2^n-1[/math]까지) x를 2진수로 표현하여 1이 들어가는 최저자리수에 해당하는 원반을 왼쪽 또는 오른쪽으로 움직이면 된다. 3회차때는 11이므로 맨위의 1번 원반이, 16회차때는 1000의 4번 원반이 이동한다.
예를 들어 3개의 원반이라면 1,2,3,4,5,6,7회차때 1번, 2번, 1번, 3번, 1번, 2번, 1번 원반을 이동하면 완성이다. 이때 위에서부터 홀수번째의 원반이 왼쪽으로 이동(쉬프트, 더이상 왼쪽에 막대가 없다면 맨 오른쪽으로 이동)하면 짝수번째는 오른쪽으로 이동(마찬가지로 오른쪽 끝에서 오른쪽으로 가야할 경우 왼쪽 끝으로 이동)하면 실수 없이 최소한으로만 움직일 수 있다. 이때 맨위의 원반이 왼쪽 또는 오른쪽으로 쉬프트하느냐에 따라 하노이의 탑이 어느쪽의 막대로 움직이는가가 달라진다. 맨위의 그림처럼 왼쪽막대의 4개의 원반에 첫 원반이 오른쪽으로 간다면 마지막엔 오른쪽 막대에 정렬되며, 첫 원반이 왼쪽으로 가면 중앙 막대에 정렬된다.
혹성탈출 : 진화의 시작 초반부에서 주인공 시저의 어미 밝은 눈이 이걸 지능 테스트용으로 한다. 그것도 엄청 빨리.
키란디아의 전설 2편 마지막에도 이 게임을 응용한 퍼즐이 등장한다.
김정훈이 출연한 일본 수학퀴즈 프로그램에서는 하노이의 탑을 변형한 문제를 냈으며, 왼쪽, 오른쪽에 5개의 원반을 가운데로 모두 옮기는 데의 최소횟수를 묻는 문제를 출제하기도 했다. 참고로 이 문제의 답은 96번이다.
매스 이펙트에서도 퍼즐로 등장한다.- ↑ 이 수열의 일반항을 구하는 방법은 다음과 같다.
관계식 [math] a_{n+1} = 2 a_n + 1[/math]을 [math] a_{n+1}+1 = 2(a_n+1) [/math]로 변형하고, [math] b_n=a_n+1 [/math]이라고 두면 [math] b_{n+1} = 2b_n [/math]이 되므로 [math] b_n [/math]는 첫째항이 [math] b_1 = a_1 + 1 = 2 (\because a_1=1)[/math]이고 공비가 [math] 2 [/math]인 등비수열이 된다. 따라서 [math] b_n = a_n + 1 = 2^{n} [/math] 이므로 [math] \therefore a_n = 2^{n} - 1 [/math]이다.