클래식 수수께끼, 하노이탑(Tower of Hanoi)

이전에 중학교 수학문제 책에서 본 기억도 있고

어디선가 책에서 본 기억도 있네요.

꽤나 어려워보이지만 알고나면 쉬워지는?(당연한건가;;)

하노이의 탑을 다루려고 합니다.

하노이탑의 유래

하노이는 지금의 베트남의 수도입니다. 이름이랑 내용이랑 매치가 안되는 부분이 있으나 당시 프랑스 식민지였던 베트남 하노이를 상징하는 국기탑에서 유래하였을걸로 '추정'하고 있습니다. 이는 프랑스 수학자 뤼카에 의해서 1883년 발표된 내용입니다.

인도의 베나레스라는 곳엔 아주 큰 사원이 있답니다. 이 사원엔 높이 50cm 정도 되는 다이아몬드 막대 3개가 있죠. 그중 가장 왼쪽막대에 세상이 만들어질 때 신이 원판들을 꽃아둡니다. 이 원판들은 도넛처럼 가운데 구멍이 뚫어져 있으며 갯수는 64개개이고 가장 커다란것부터 아래에 놓도록하여 쌓아두었다 합니다.

이 장치를 만든 신은 승려들에게 밤낫을 쉬지않고 원판을 한장씩 옮겨 다이아몬드의 막대의 반대쪽 끝으로 모두 옮겨놓도록 지시합니다. 그러면서 규칙도 함께 말해주었다고 하네요. 그러면서 이 명령이 완료가 되면, 세상에 종말이 온다고 했습니다.

지금도 옮기고 있을까요?? 그럼 세상에 종말은 언제쯤 올까요??

하노이탑의 규칙

1. 한쪽끝의 탑을 아래 규칙에따라 다른쪽끝으로 같은모양이 되도록 옮겨야 합니다.

2. 한번에 한개의 원판만 옮길 수 있습니다.

3. 작은원판위에 그것보다 큰 원판이 올라갈 수 없습니다.

본격 옮겨보기

음.. 자작이미지라 그런지 깔끔치 못한점 죄송합니다;;; 무료이미지가 없드라구요 하노이탑이;;;

여기까지 왔으면 이제 [1]번은 첫번째 막대로 옮기고, [3]번을 세번째 막대로 옮기고, [1]번을 빈막대로 옮긴뒤, [3]번 위에 [2]번 [1]번 순으로 올려주시면 이동이 완료됩니다.

그치만 원판이 4개 이상이면 너무 어려울 것 같아요

그치만 이렇게 생각해보시면 됩니다. 3개 이상일 때도 이 방법이 적용될 수 있으며 4개뿐만이 아니라 10개, 100개 여도 처리할 수 있습니다.

이와같이 맨아래하나와 나머지, 총 두부분으로 나누어 생각해봅시다. 원판이 두개라고 생각하는 거죠. 그리고 아래와같이 실제 두개를 옮기는 것 처럼 해결을 하시면 됩니다..

그치만 한번에 한번의 원판만 이동할 수 있다면서요?? 그 법칙이 무시된건 아닌가요?


생각을 이렇게 커다랗게 두부분으로 나눠서 해서 그렇게 생각이 들 수 도 있습니다.
그러나 위의 그림의 의미는 [1],[2]를 가운데로 옮기는작업을 끝낸후에 [3]을 세번째 기둥으로 옮기라는 의미이므로 문제가 없습니다.


음 위에는 생각 흐름대로 하다보니 여기서 제가 말씀드린 것과는 조금 다르게 되버렸네요. 그치만 [1],[2]가 모여서 만드는 탑이 위치만 달랐을 뿐 푸는 방법은 같다는거 아시면 되겠습니다.


그럼 실제로 64개의 원판을 옮기라고 신이 명 했던건 시간이 얼마나 걸릴까요??
방법은 금방 말씀드린것처럼 맨아래 1개와 나머지 63개를 하나로 보아 총 두 부분으로 나눈뒤 2개를 옮기는 것 처럼 해주시면됩니다... 그럼 63개는 어떻게 옮기냐구요?? 63개중 맨 아래 1개와 나머지 62개로 두 부분으로 나누어 두개를 옮기듯 하면 됩니다....


이렇게 해서 걸리는 시간은 5849억 4241만 7355년 후 라고합니다. 세상이 멸망하긴 아직 너무 이른 것 같습니다. 승려들이 있었다는건 인류가 태어난 이후라는 이야기니까요.

티케비 다른 이야기

1. 옷에 뭔가 묻었을 때 이렇게 대처하면 쉽다
2. 소셜커머스 어디까지 믿어야될까??
3. 공복의 물한잔 건강에 좋을까??
   
4. 생활속 다리미의 특별한 용도 두가지
5. 갑자기 생긴 벌집 어떻게 처리해야 현명할까? (2)
6. 우유가 건강에 해롭다는게 사실일까?
   
7. 엘리베이터 추락시 점프하면 살 수 있을까? (2)
8. 윤년(2월 29일)에 태어난 사람의 생일은 4년에 한번씩 가질까?
9. 군부대의 자극적인 문구 마치 70년대 같다 (2)
10. 집안에 날파리 없애는법 퇴치법