하노이 탑의 최단 이동 횟수 알아 보기 제주 북초등학교 6학년 심화반 임 성 찬

목 차 주제 선정 동기 하노이 탑의 전설 하노이 탑의 규칙 하노이 탑 옮겨 보기 기둥이 세 개일 때 최단 횟수로 옮기는 법 기둥이 네 개일 때 최단 횟수로 옮기는 법 하노이 탑의 전설을 푸는 데 걸리는 시간 알아 보기 프로젝트 학습을 마치고 나서

1. 주제 선정 동기 내가 하노이 탑을 주제로 삼은 이유는 5학년 때 했던 파스칼의 삼각형과 소마 큐브를 하고 나서 딱딱한 수학 보다는 부드럽고 재미있는 문제 풀이를 해보고 싶었는데, 그 때 마침 하노이 탑의 전설이라는 글을 읽고 하노이 탑을 하기로 결심을 굳혔다.

인도의 바라문교라는 종교의 사원에는 다음과 같은 전설이 전해지고 있다고 한다 2. 하노이 탑의 전설 인도의 바라문교라는 종교의 사원에는 다음과 같은 전설이 전해지고 있다고 한다 신이 천지를 창조한 후, 세 개의 기둥을 만들었는데, 한 기둥에는 64개의 원판이 꽂혀 있었고, 모든 원판들이 마지막 기둥으로 옮겨지면 세상의 종말이 온다.

3. 하노이 탑의 규칙 이게 바로 하노이 탑! 원판은 한번에 하나만 옮길 수 있다. 작은 원판 위에 큰 원판을 올려 놓을 수 없다. 위에 아무 원판도 없는 원판만 이동 시킬 수 있다. ※ 이러한 조건으로 풀지 않을 경우 하노이 탑을 풀 때 혼란에 걸리게 된다 이게 바로 하노이 탑!

4. 하노이 탑 옮겨보기 1. 원판 3개로 해보기 결과 : 7번 하니 세 개 모두 다른 기둥으로 이동 된다. 2. 원판 4개로 해보기 결과 : 여러 번 해본 결과 15번이 가장 최단 횟수다. 3. 원판 5개로 해보기 결과 : 최단 횟수로 31번이 나왔다.

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 ※ 기둥이 세 개이고 원판이 3개 라고 가정했을 때이다. 이게 하노이 탑이라고 하면. 1 2 3 2 3 1

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 1. 1번 원통을 2번 기둥에 놓는다. 1 2 3 2 3 1

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 2. 2번 원통을 3번 기둥에 놓는다 1 2 3 3 1 2

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 3. 1번 원통을 2번 위에 놓는다. 1 2 3 1 3 2

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 4. 3번 원통을 2번 기둥에 놓는다. 1 2 3 1 3 2

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 5. 1번 원통을 1번 기둥에 놓는다. 1 2 3 1 3 2

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 6. 2번 원통을 3번 위에 놓는다. 1 2 3 2 1 3

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 7. 1번 원통을 2번 위에 놓는다. 1 2 3 1 2 3

5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 여기서 알 수 있는 규칙! 홀수는 짝수 위에 놓고 짝수는 홀수 위에 놓는다. 여기서 알 수 있는 규칙! 홀수는 짝수 위에 놓고 짝수는 홀수 위에 놓는다. 1 2 3 1 2 3

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 1. 원판이 3개 일 때 결과 : 5번이 최단 횟수로 나왔다. 2. 원판이 4개 일 때 결과 : 9번이 최단 횟수로 나왔다. 3. 원판이 5개 일 때 결과 : 13번이 최단 횟수로 나왔다.

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 ※ 아까 보다 기둥이 하나 늘어났다고 가정한 것이다. 기둥이 네 개이고 원통이 4개라고 가정한 것이다. 1 2 3 4 1 2 3 4

5. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 1. 1번 원통을 2번 기둥으로 옮긴다. 1 2 3 4 2 3 4 1

5. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 2. 2번 원통을 3번 기둥으로 옮긴다. 1 2 3 4 3 4 1 2

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 3. 3번 원통을 4번 기둥으로 옮긴다. 1 2 3 4 4 1 2 3

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 4. 1번 원통을 2번 원통 위로 옮긴다. 1 2 3 4 1 4 2 3

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 5. 4번 원통을 2번 기둥으로 옮긴다. 1 2 3 4 1 4 2 3

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 6. 3번 원통을 4번 원통 위로 옮긴다. 1 2 3 4 3 1 4 2

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 7. 1번 원통을 4번이나 1번 기둥으로 옮긴다. 1 2 3 4 3 1 4

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 8. 2번 원통을 3번 원통 위로 옮긴다. 1 2 3 4 2 3 1 4

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 9. 1번 원통을 2번 원통 위로 옮긴다. ※ 그러므로 기둥 네 개는 기둥 3개 보다 빨리 옮길 수 있다. 1 2 3 4 1 2 3 4

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 원판의 수를 n이라고 하고 기둥의 개수가 4개일 경우 다음과 같은 패턴이 존재한다는 것을 알아내었다. 원판 수 원판의 이동 (원판의 번호) 원판 이동 횟수 N=1 ① 1번 N=2 1②1 3번 N=3 12③21 5번 N=4 1232④2321 9번 N=5 123214⑤412321 13번 N=6 12321454⑥45412321 17번 N=7 123242321565⑦565123242321 25번

6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 결론: 원판의 개수(n) 1 2 3 4 5 6 7 8 9 10 11 12 13 원판 이동 횟수 17 25 33 41 49 65 81 97 이동{n-(n-1)} - 16 원판 이동 횟수의 규칙 n번째와 n-1 번째 원판 이동 횟수의 차는 2의 거듭제곱 꼴이다. 2⁰이 처음 1이고, 2의 제곱이 다음 2번, 2의 2제곱이 그 다음 3번,… 순으로 간다.

7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용) ※전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? (1)어림잡아 계산 해 보기 ☞ 64개의 원판을 모두 옮기려면 2⁶⁴-1초가 걸리게 된다. 2를 10번 곱한 것이 1024 인데, 이를 약 1000이라고 반올림을 한 후, 2를 60번 곱한 값에 4번 더 곱한(16을 곱한) 값을 구하면 된다. 즉, 2를 60번 곱한 값은 약 1,000,000,000,000,000,000이므로 곱하기 16을 하면 16,000,000,000,000,000,000초 가 된다. 1분은 60초 이고, 1시간은 60분 이므로 3600초, 하루는 24시간 이므로 86400초이다. 또 1년은 365일 이므로 약 3억 초 이다. 그래서 16,000,000,000,000,000,000/300,000,000=5.333×100,000,000,000= 약 5333억 년 이 된다.

7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용) 전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? (2)계산기를 이용해 보다 정확히 계산하기 ☞2⁶⁴-1=18,446,744,073,709,551,615(초) = 약 584,942,417,355(년) = 약 5849억 (년)이 된다.

7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용) ※전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? ※ 이 문제를 더 빠르게 해결하는 방법 을 생각해 보기로 하였다. 그 후 나온 생각 3가지가 있다. 0.5초에 원통을 하나씩 옮긴다.(거의 불가능함) 신께서 인간에게 자비를 베풀어 원판의 수를 하나 줄여준다.(시간 ½로 단축됨) 하노이 탑의 기둥을 한 개 늘린다.( 그렇게 되면 5시간 7분 13초면 모든 원통을 다른 곳으로 옮길 수 있다.)