[목차] == 전설 == 1883년 프랑스의 수학자 에두아르드 뤼카(Lucas,E. : 1842~1891)가 처음으로 발표한 게임이다. 이후 여러 사람을 거치면서 다음과 같은 전설이 덧붙여졌다. >"고대 인도 베나레스에 있는 한 사원의 이야기" >여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 63개(혹은 64개)의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다. >이 규칙으로 63(64)개의 원판을 처음 놓여있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다. 이 가짜 전설 덕분에 인도에 있는 베나레스(현재 이름은 바라나시)가 베트남의 [[하노이]]와 같은 곳인 줄 아는 사람들이 꽤 많은듯. 이 규칙들을 이용하여 63(64)개의 원판을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 [math( 2^n - 1 )]번이기 때문이다. [math( n )]번째 원반을 한쪽 기둥으로 옮기는 데 필요한 최소 횟수를 [math( a_n )]라고 하자. [math( (n+1) )]번째 원반을 옮기려면([math( a_{n+1} )]을 구하려면) [math( n )]번째 까지의 원반을 한쪽 기둥으로 옮기고([math( a_n )]를 더하고) [math( (n+1) )]번째 원반을 비어있는 기둥에 옮기고([math( 1 )]을 더하고) [math( n )]번째까지의 원반을 [math( (n+1) )]번째 원반 위로 옮기면([math( a_n )]를 다시 더하면)된다. 따라서 [math( a_1 = 1, a_{n+1}=2a_n+1 )]이고 이 [[점화식]]에 의한 수열 [math( a_n )]의 일반항을 구해보면 [math( a_n=2^n - 1 )]가 나온다.[* 이 수열의 일반항을 구하는 방법은 다음과 같다.[br]관계식 [math( a_{n+1} = 2 a_n + 1)]을 [math( a_{n+1}+1 = 2(a_n+1) )]로 변형하고, [math( b_n=a_n+1 )]이라고 두면 [math( b_{n+1} = 2b_n )]이 되므로 [math( b_n )]는 첫째항이 [math( b_1 = a_1 + 1 = 2 (\because a_1=1))]이고 공비가 [math( 2 )]인 등비수열이 된다. 따라서 [math( b_n = a_n + 1 = 2^{n} )] 이므로 [math( \therefore a_n = 2^{n} - 1 )]이다.] 따라서 63개의 원반을 완전히 옮기는 데 걸리는 횟수는 [math( 2^{63} - 1 )], 자그마치 922경 3372조 368억 5477만 5807회에 달한다. 판을 한 번 옮기는 데 1초가 걸린다 해도 약 2922억 7천만 년이 걸리는데[* 이 시간은 64비트 정수형으로 시간을 표기하는 시스템이 한계에 도달하는 데에 필요한 시간과도 같다. 원반이 64개인 경우에는 이의 2배인 약 5845억 5천만 년. 자세한 내용은 [[2038년 문제]] 문서로.], 이는 우주의 나이인 130~135억년보다도 훨씬 길며 중소형 [[적색왜성]]의 예상 수명과 맞먹는 시간이다. 심지어 적색 왜성이 수명을 다하기도 전에 우주가 멸망할 수도 있다. 하지만 만약 막대를 하나 더 추가해서 네 개로 만든다면 최소 18,433번만 옮기면 되는데, 1초에 판을 1개 옮긴다 할 때 5시간 7분 13초면 된다. == [[퍼즐]] == [[파일:external/437a6637b1f6834a74146f6e51b7360fa64116c23c3c0c7fd5462db9a8a73ab4.jpg]] 1의 이야기에서 따와 3개의 기둥에 적당한 개수의 원반을 쌓아 놓고 다른 쪽으로 옮기는 게임. 원반 개수가 늘어날수록 이동 횟수가 엄청나게 늘어나기 때문에 많아야 7, 8개 정도만 쓰며 소모 시간으로 승부를 짓는 것이 보통인데, 이 정도면 1초에 원반 하나를 옮긴다 가정할 때 2~4분 정도 걸린다. [[프로그래밍]] 공부를 하는 사람들의 초반의 벽이 이것의 알고리즘을 구현하는 것. 보통 [[재귀함수]]에 대해 공부할 때 예제로 쓰기 좋아 한번쯤은 보고 넘어가는 문제이다. 구현한다면 다음과 같다. {{{#!syntax cpp int Hanoi(int from, int to, int n) // from번 기둥에서 to번 기둥으로 n개의 원반을 이동. { if(n == 1) { printf("%d번 기둥에서 %d번 기둥으로 이동\n", from, to); return 0; } Hanoi(from, 6-from-to, n-1); printf("%d번 기둥에서 %d번 기둥으로 이동\n", from, to); Hanoi(6-from-to, to, n-1); return 0; } }}} 재귀를 사용하지 않는 경우의 알고리즘은 다음과 같다. 원반의 총 개수를 [math(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개의 원반에 첫 원반이 오른쪽으로 간다면 마지막엔 오른쪽 막대에 정렬되며, 첫 원반이 왼쪽으로 가면 중앙 막대에 정렬된다. == 기타 == [[혹성탈출: 진화의 시작]] 초반부에서 주인공 [[시저(혹성탈출 시리즈)#s-2|시저]]의 어미 [[밝은 눈]]이 이걸 지능 테스트용으로 하는데, 무척 빨리 완성하는 모습을 볼 수 있다. [[키란디아의 전설]] 2편 마지막에도 이 게임을 응용한 퍼즐이 등장한다. 김정훈이 출연한 일본 수학퀴즈 프로그램에서는 하노이의 탑을 변형한 문제를 냈는데, 왼쪽, 오른쪽에 있는 5개의 원반을 가운데로 모두 옮기는 데 최소 몇 번 움직여야 하느냐하는 문제. 답은 96번. [[매스 이펙트]]에서도 퍼즐로 등장한다. [[레이튼 시리즈]]에서는 단골로 나오는 문제 유형이다. [[유희왕 VRAINS]]의 악역 조직 [[하노이의 기사]]는 여기에서 이름을 따왔는데, 3화의 수업장면에서 이 퍼즐을 설명하는 것으로 나왔다. 또한 29화에서 [[리볼버(유희왕)]]의 독백으로 다시 언급되며, 작중에서는 방대한 양의 데이터를 원반으로 흡수한 뒤 이를 단번에 출력해 네트워크 전체를 파괴하는 EMP 병기로 등장했다. 이후 2기에서는 무기 대신 스캔 프로그램을 설치하여 라이트닝의 은신처인 미러 링크 브레인즈 서버를 찾아낸다. [[대항해시대 3]]에 나오는 미니게임 중 하나로 등장한다. [[스텔라리스/NPC|스텔라리스의 수호자들]] 중 수수께끼의 요새 이벤트를 시작할 시 볼 수 있는 퍼즐이다. "기둥 세 개가 있고 그 중 하나에는 고리 세 개가 크기 순서대로 쌓여있습니다." 정답은 "다른 기둥에 고리들을 재배열한다"로, 상술한 퍼즐의 규칙과 일치한다. [[분류:장난감]][[분류:퍼즐]]