하노이의 탑
하노이의 탑은 고전적인 수학 퍼즐입니다. 기둥 세 개, 크기가 서로 다른 원판 더미, 그리고 엄격한 규칙 두 가지. 한 번에 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 절대 놓지 않는 것입니다.
기둥 세 개와 원뿔 모양의 원판
판에는 기둥이 세 개 있습니다. 원판은 모두 크기가 다르고 기둥에 끼울 수 있습니다. 처음에는 원판 전체가 한 기둥에 크기순으로, 가장 큰 것이 맨 아래, 가장 작은 것이 맨 위에 놓여 있어 더미가 원뿔 모양입니다. 목표는 그 탑 전체를 다른 기둥으로 옮기는 것입니다.
세 가지 규칙
1. 한 번에 원판 하나만 옮깁니다. 2. 한 번의 이동은 한 더미의 맨 위 원판을 집어 다른 더미나 빈 기둥에 놓는 것입니다. 3. 큰 원판은 절대 작은 원판 위에 놓일 수 없습니다. 이 세 가지 규칙이 게임의 전부입니다. 이 규칙 아래에서 허용되는 모든 배치는 각 기둥의 순서를 유지하면서 원판을 기둥에 나누어 놓는 방법입니다.
가장 짧은 풀이는 2ⁿ − 1
원판 n개짜리 탑을 푸는 최소 이동 횟수는 2ⁿ − 1입니다. 원판 하나는 1번, 둘은 3번, 셋은 7번, 넷은 15번, 다섯은 31번이 걸립니다. 원판이 하나 늘 때마다 이전 풀이가 두 배가 되고, 가장 큰 원판을 옮기는 한 번이 더해집니다. n − 1개에 T번이 걸리면 n개에는 2T + 1번이 걸립니다. 이 점화식이 정확히 2ⁿ − 1입니다. PictorX 앱에서 가장 높은 탑인 원판 8개는 255번이 걸립니다. 이보다 짧은 합법적인 경로는 없습니다.
재귀는 어떻게 작동할까
남은 기둥을 보조 기둥으로 써서 원판 n개를 시작 기둥에서 목표 기둥으로 옮기려면: 1. 위쪽 n − 1개 원판을 시작 기둥에서 보조 기둥으로 옮깁니다. 2. 가장 큰 원판을 시작 기둥에서 목표 기둥으로 바로 옮깁니다. 3. n − 1개 원판을 보조 기둥에서 목표 기둥의 가장 큰 원판 위로 옮깁니다. 2단계가 허용되는 것은 가장 큰 원판은 어느 기둥에나 놓일 수 있기 때문입니다. 1단계와 3단계는 원판이 하나 적은 같은 퍼즐입니다. 호출은 원판 하나에서 끝나며, 그 원판은 한 번 움직입니다. 이를 펼치면 2ⁿ − 1번의 이동이 나오고, 어느 단계도 큰 원판을 작은 원판 위에 놓지 않습니다.
금 원판 64개의 전설
프랑스 수학자 에두아르 뤼카는 1883년에 이 퍼즐을 소개했습니다. 그는 퍼즐과 함께 카시 비슈와나트의 한 인도 사원에 관한 전설을 들려주었습니다. 그곳의 사제들이 같은 규칙에 따라 금 원판 64개를 옮기고 있으며, 마지막 이동이 끝나면 세상이 끝난다는 이야기입니다. 원판 64개는 2⁶⁴ − 1번, 즉 18,446,744,073,709,551,615번의 이동이 필요합니다. 밤낮으로 1초에 한 번씩 실수 없이 옮겨도 약 5,850억 년이 걸립니다. 사제들은 끝내지 못할 것입니다.
PictorX에서 해 보기
하노이의 탑을 열면 시작 기둥에 원판 네 개짜리 탑이 이미 놓여 있습니다. 최소 15번이면 됩니다. 맨 위 원판을 다른 기둥으로 끌거나, 기둥을 클릭한 다음 원하는 기둥을 클릭하세요. 1, 2, 3 키도 같은 일을 합니다. 큰 원판을 작은 원판 위에 놓으면 거부됩니다. ‘원판’은 1부터 8까지 고를 수 있어서 1, 3, 7, 15, 31, 63, 127, 255를 공식과 비교해 볼 수 있습니다. ‘단계’는 가장 짧은 풀이의 한 수를 재생합니다. ‘풀기’는 나머지를 재생합니다. ‘원판 3개 보기’는 재귀 전략이 움직이는 모습을 보여 줍니다. ‘실행 취소’와 ‘다시 실행’으로 이동 기록을 오갈 수 있습니다. PNG로 저장하거나 PictorX 편집기에서 판을 여세요.
자주 묻는 질문
하노이의 탑 규칙은 무엇인가요?
한 번에 원판 하나씩 옮깁니다. 기둥의 맨 위 원판을 집어 다른 기둥에 놓습니다. 큰 원판을 작은 원판 위에 놓으면 안 됩니다. 탑 전체가 한 기둥에서 시작해 다른 기둥에서 끝나야 합니다.
가장 짧은 풀이는 몇 번 이동하나요?
2ⁿ − 1번입니다. 원판 하나는 1번, 둘은 3번, 셋은 7번, 넷은 15번, 다섯은 31번입니다. 원판이 하나 늘 때마다 이전 풀이가 두 배가 되고 한 번이 더해집니다.
하노이의 탑은 누가 만들었나요?
프랑스 수학자 에두아르 뤼카가 1883년에 소개했습니다. 카시 비슈와나트의 사제들과 금 원판 64개 이야기는 그가 퍼즐에 덧붙인 전설입니다.
원판 64개는 얼마나 걸릴까요?
2⁶⁴ − 1번, 즉 18,446,744,073,709,551,615번입니다. 1초에 한 번씩 옮기면 약 5,850억 년이 걸립니다.
관련 도구
하노이의 탑
브라우저에서 원판 탑을 기둥 세 개 사이로 옮겨 보세요. 한 번에 하나씩, 큰 원판은 절대 작은 원판 위에 놓지 않습니다. 가장 짧은 풀이는 2ⁿ − 1번입니다.
뷔퐁의 바늘
브라우저에서 줄이 그어진 바닥에 바늘을 떨어뜨리세요. 교차 횟수를 세고 뷔퐁의 1777년 실험이 π를 추정하는 과정을 지켜보세요.
뷔퐁의 바늘
뷔퐁의 1777년 바늘 문제: 평행선 위에 떨어뜨린 바늘이 왜 π를 추정하는지, 짧은 바늘의 확률 2l/(πd)가 사인 곡선 아래 넓이에서 어떻게 나오는지, 그리고 왜 실험이 느리게 수렴하는지 알아봅니다.
곱셈 원
원 위의 각 수를 그 배수와 이으세요. 종이에, 분필로, 또는 나무 위에 곱셈표, 카디오이드, 실 그림을 그려 보세요.
콜라츠 추측
브라우저에서 콜라츠 3n+1 문제를 탐험하세요. 우박수열을 따라가고, 기하학적 콜라츠 나무를 키우고, 연속 콜라츠 프랙털을 확대해 보세요.
랭턴의 개미
브라우저에서 랭턴의 개미를 실행하세요. 대칭, 혼돈, 104걸음 고속도로를 지켜본 뒤 여러 색 규칙, 여러 마리의 개미, 육각 격자, 터마이트를 시험해 보세요.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
하노이의 탑 하기