답변자님,
정보를 공유해 주세요.
동판에 막대가 세 개 있고, 크기가 서로 다른 4 개의
원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로
원판을 다른 막대로 모두 옮기는 놀이를 생각해 봅시다.
(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래쪽에
있어야 한다.
그러면 원판을 모두 다른 막대로 옮기는데 필요한 최소
이동회수는 모두 몇 번 인가 알아보시오.
| |||||||
하노이탑 문제 (Hanoi Tower Problem)
지난 강좌의 비둘기집 원리에 이어서 이산수학에서의 전형적인 예로 다음을 알아봅시다.
1883년 프랑스 수학자 Edouard Lucas가 제시한 다음과 같은 하노이 탑 문제 (Hanoi Tower Problem) 를 생각하여 봅시다.
Vietnam의 Hanoi시 외곽에 있는 Benares사원의 한가운데 있는 Dome에 다음과 같은 전설이 쓰여져 있는 동판이 있다.
동판에 다이아몬드막대가 세 개 있고, 크기가 서로 다른 64개의 황금 원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 황금 원판을 다른 막대로 모두 옮기는 놀이를 신(God)이 하고 있다. (1) 한 번에 한 개의 황금 원판만을 옮긴다. (2) 크기가 큰 황금 원판은 반드시 크기가 작은 황금 원판 아래쪽에 있어야 한다. 그러면 신이 이 놀이를 다 마칠 때면 (즉, 황금 원판이 다른 막대로 모두 옮겨졌다면), 이 세상은 연기처럼 사라질 것이다.
위의 무시무시한 전설은 실제로 황금 원판을 한 개 움직이는데 1초가 걸린다면, 황금 원판이 다른 막대로 모두 옮기는데 걸리는 시간은 대략적으로 5,000 억년 이상이 되고, 실제로 우리가 살고 있는 태양계의 추정 수명은 5,000 억년 미만이므로, 이 세상은 연기처럼 사라질 것이다라는 이야기는 과학적으로 증명할 수 있는 사실이기도 하다. (우리가 여러 가지 역사적 사실에서 알 수 있듯이, 예전의 우리 선조들은 놀랍도록 과학적이다 !) 그러면 위의 하노이탑 문제는 어떻게 해결할 수 있는가 알아보도록 하자. 먼저 하노이탑 문제를 일반적으로 기술하면 다음과 같다.
이러한 문제는 전형적인 귀납적사고를 필요로 하는 문제이다. 즉, 특별한 몇 가지의 경우를 관찰하여 일반적으로 적용할 수 있는 규칙을 추론하고 이를 엄밀하게 수학적으로 증명하는 과정을 거쳐 문제를 해결하도록 합시다.
이제 원판이 두 개 뿐이면, 우리는 다음 그림과 같은 단계로 원판을 움직일 수 있다.
따라서 필요한 원판의 이동회수는 3 회이다.
이제 일반적으로 n개의 원판이 있을 때 필요한 원판의 이동 회수를 알아보도록 하자. 이 경우의 풀이전략은 다음과 같다.
먼저 n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를 P(n) 이라고 하자. 그러면, P(1) = 1 P(2) = 3 P(3) = 7
임을 알 수 있다. 일반적으로 P(n)은 P(n-1)로 부터 유도할 수 있다. 즉, 다음의 그림을 참고하여 생각하여 보자.
위의 그림을 보면, 모든 자연수 n에 대하여 우리는 관계식 P(n) = 2 P(n-1) + 1 을 추측할 수 있다. 위와 같은 인접한 항과의 관계식을 우리는 점화식 (recurrence formula) 라고 한다. [이에 관하여 우리는 다음에 자세히 학습하도록 한다.] 그러면 위 점화식에 차례로 대입하여 알아보면
등비수열의 합 공식을 이용하면, 일반적으로
구체적으로 검산하여 보면, 우리는 위의 식이 옳음을 알 수 있다. 따라서, 원래의 하노이탑 문제의 경우는 n = 64 인 경우이므로 필요한 원판의 이동 총수 (이것은 가장 최소의 이동 회수를 의미하며, 만약 이동순서를 잘못하면 그만큼 이동회수는 늘어 난다. ) 는
대략 1847 해 (해는 조 단위의 다음 단위)만큼의 이동이 필요하며, 만약 1번의 움직임에 1초가 걸린다고 가정하면, 대략 5000억년 이상이 걸리게 된다. 따라서 이 게임이 끝나게 되면 5000억년 이상의 시간이 경과한 이후이며, 그러면 우리 태양계의 운명도 끝이 난 이후일 것이다. 예전의 우리 선조들의 수학계산 능력이 매우 뛰어남을 짐작을 할 수 있다 (아마도 위와 같은 계산을 하였을까는 학생들의 상상에 맞기도록 합시다.)
이제 하노이탑 문제를 일반화할 수 있는 여러 방법에 대하여 알아보도록 하자.
먼저 다음과 같은 상황을 생각할 수 있다.
위 문제는 하노이탑 문제를 일반화할 수 있는 여러 방법 중 가장 간단한 모양이다. 문제의 가정에서 같은 크기의 2장의 원판은 똑같은 것으로 생각한다고 하였으므로, 2개의 같은 크기의 원판을 계속하여 같은 막대로 옮긴다고 가정하면, 이는 2개의 원판을 한꺼번에 움직인다고 생각하여 계산하여도 될 것이다. 따라서, 우리는 일반화된 하노이탑 문제에서 2n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를 A(2n)이라고 하면, 관계식
을 짐작할 수 있다.
위의 상황을 더욱 일반화하면 다음과 같이 생각할 수 있다. 크기 k 인 원판은 nk개이고, m 개의 서로 다른 크기를 갖는 일반화된 하노이 탑의 경우 총 n1+ n2 +... + nk 개의 원판을 모두 옮기는데 필요한 원판의 이동회수 A ( n1,n2,..., nk) 는 얼마인가 등 여러 가지 다양한 일반화를 생각할 수 있다.
이에 관하여는 참고문헌[ Knuth and et-al.]에 있는 Knuth의 책을 참고 하기 바랍니다. |
2008.01.19.
-
채택
지식인 채택 답변입니다.
-
출처
emath
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
생각보다 간단하더군요...
세개 기둥을 왼쪽부터 1, 2, 3 이라고 할때..
1에서 3으로 옮기는 거잖아요..
그런데 홀수면 제일 작은 원판을 옮기고자 하는 기둥 방향으로 옮기시면 되구요..
짝수이면 제일 작은 원판을 그 반대쪽 기둥에 옮기시면 됩니다..
언제나 순서는 무조건 차례대로 만드는 겁니다.. 크기순으로..^^
한마디로 10개든 20개든 방법은 똑같습니다.. 3개짜리만 해결되면.
똑같은 방법으로 하면 됩니다..
3개니.. 당연히 제일 작은걸 3번에 놓고 중간크기를 2번에 놓고..
다시 제일 작은걸 2번으로 옮기고 그다음 제일 큰걸 3번으로 옮기고
그럼 2번 기둥에 원판이 두개로 짝수가 되잖아요..그럼 옮기고자 하는 반대 방향으로.
제일 작은걸 1번으로 옮기고 중간크기 원판을 3번으로 옮기고 다시 1번에 있는 제일 작은걸
3번으로 옮겨 마무리 하면 됩니다.. 갯수에 상관없이 전부 이런 방법입니다..
6개짜리면.. A,B,C,D,E,F 원판으로 해설해 드리겠습니다..
6개면.. 짝수잖아요..
그러니 A원판을 2번으로 옮기시고 B원판을 3번으로 옮기시고 다시 A를 3번으로 옮기시고
C번을 2번으로 옮기세요 그럼 3번기둥에 A,B번 원판 짝수가 되잖아요.. 그럼 A번을 1번으로 옮기시고
B를 2번으로 옮기시고 다시 A를 2번으로 옮깁니다..
그럼 2번기둥에 A,B,C가 1번기둥엔 D,E,F가 있습니다.
그다음 D를 3번으로 옮기시고 2번 둥이 홀수가 되죠?? 그럼 옮겨야 되는 방향으로 (지금은 맨 밑판이 D가 되므로
3번기둥으로 옮겨야 됩니다.) A를 3번으로 옮기시고 B를 1번으로 옮기시고 다시 A를 1번으로 옮기시고..
C를 3번으로 옮기세요 그럼 1번기둥에 A,B,E,F 3번기둥에 C,D가 있죠..
그럼 1번에 A,B를 3번으로 옮겨야 되죠?? ^^ 짝수 그럼게 되면 옮겨야 되는 방향의 반대방향으로 시작해야 됩니다.. A를 2번으로 옮기시고 B를 3번으로 다시 A를 3번으로 옮기시면...
현재 E,F만 1번기둥에 3번기둥엔 A,B,C,D가 있게 됩니다..^^
그럼 1번 기둥이 다시 짝수가 되죠??
그렇게 되면 시작은 옮기고자 하는 반대방향으로 시작합니다..
E를 2번으로 옮기시고 그럼 3번기둥에 4개..(A,B,C,D)를 2번 기둥으로 옮깁니다..
짝수니 당연히 옮기고자 하는 반대방향으로 시작해야 겠죠..
A를 1번으로 옮기시고 B를 2번으로 옮기시고 다시 A를 2번으로 옮깁니다..
그리고 C를 1번으로 옮기시고 다시 A를 3번으로 옮기시고 B를 1번으로 옴기시고..
다시 A를 1번으로 옮기세요.. 그다음 D를 2번으로 옮기시면..
1번기둥에 A,B,C,F 2번 기둥에 D,E 가 남을 겁니다..
그렇게 되면 1번 기둥의 원판 A,B,C를 2번 기둥으로 옮겨야 하기 때문에...
옮길 원판 세개 홀수.. A를 옮겨야 할 방향으로 옮깁니다..
A를 2번으로 옮기시고 B를 3번으로 옮기시고 다시 A를 3번으로 옮기시고 C를 2번으로 옮깁니다..
그다음 3번엔 A,B 짝수 똑같이 반대방향으로 A를 1번으로 B를 2번으로 옮기세요..
그리고 다시 A를 2번으로 옮기시면..
1번 기둥엔 F 원판 한개만 남고.. 2번 기둥엔 A,B,C,D,E 다섯개의 원판이 이동한 상태죠..^^
이제 마지막 원판을 3번으로 옮깁니다..^^ 차례대로 3번 기둥으로 옮겨봅시다..ㅋ
먼저 1번에 F (홀수) 3번으로 옮깁니다..
그럼 2번의 원판을 3번으로 옮겨야 겠죠..
일단 2번원판의 갯수는 전부 5개 홀수입니다..
그럼 A는 옮기고자 하는 방향 3번으로.. 시작합니다..
B를 1번으로 옮기고 다시 A를 1번으로 옮기고 C를 3번으로 옮기세요
그다음 A를 2번으로 옮기고 B를 3번으로 옮기고 A를 3번으로 옮기세요..^^
현재 1번은 비어있구요 2번에는 D,E가 있고 3번에는 A,B,C,F 가 있습니다..^^
이제 D를 1번으로 옮기고 3번에 있는 A,B,C를 1번으로 옮기는 겁니다..
옮길것이 홀수 이므로 A를 1번으로 옮기고 B를 2번으로 옮기고 다시 A를 2번으로 옮기고
C를 1번으로 옮깁니다 그다음 A를 3번으로 옮기고 B를 1번으로 옮기고 다시 A를 1번으로 옮깁니다.
그리고 E를 3번으로 옮기면.. 1번에는 A,B,C,D가 3번에는 E,F가 있습니다..
그럼 1번기둥에 A,B,C,D 4개 이므로 시작은 2번 기둥으로 시작합니다..
A를 2번으로 옮기고 B를 3번으로 옮기고 A를 3번으로 옮깁니다.
그다음 C를 2번으로 옮기고 A를 1번으로 옮기고 B를 2번으로 옮기고 A를 2번으로 옮깁니다..^^
그리고 D를 3번으로 옮기면 1번기둥엔 원판이 없고 2번기둥엔 A,B,C 3번기둥엔 D,E,F가 남습니다..
2번 기둥에 A,B,C 홀수이니 옮기고자 하는 방향으로 시작합니다..^^
A를 3번으로 B를 1번으로 다시 A를 1번으로 그리고 C를 3번으로 옮깁니다.
그다음 A를2번으로 B를 3번으로 다시 A를 3번으로 옮기시면 The End 입니다..^^
일부러 풀어서 적어봤어요.. 한번 적힌대로 하시면서 습득 하시는게
이해하시는데 더 빠를듯 싶어서요..
위에도 말씀드렸듯이 그냥 공식 같지도 않은 공식입니다..
옮겨야 할 판의 밑판.. ( A,B,C,F 면 A,B,C 로 이어진 판의 갯수만 생각합니다..^^ C를 밑판으로 보죠)
까지의 갯수에 따라 A의 갈길이 결정되니 이점만 주의 하시면.. 정말 쉽게 하실수 있을 겁니다..
(뭐 수백개라도 옮기실수 있을 거에요..^^ 수백개라면..ㅋ 문제는 시간.;; 살아실제 가능하실지..;;)
2008.01.22.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
저도 이 문제 때문에 고민을햇는데 이렇게생각하면 쉽더라구요
2의n승-1
ex)두개일경우 2x2-1= 3임
이렇개하면 6개면 2X2X2X2X2X2=64
64-1=63
이렇게 쉽게나오는거죠
이상허졉한답변이엿습니당
채택부탁 ㅎ
2008.01.23.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
2008.02.17.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
질문자인사 좋은 답변 감사합니다. 많은 도움이 되었습니다.
하노이탑이 요렇게 생겼구요.
규칙은요.
한번에 한개의 원판을 움직일 수 있다는 것과 작은원판위에 큰원판을 놓을수 없다는게 규칙입니다.
해보고 싶으시면 여기 들어가서 해보세요~
http://puzzllo.co.kr/flash/flash/hanoi/hanoi.html
출처 : 그림 : 네이버블로그
2008.09.30.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
