하노이 탑과 점화식 > 중.고등교육 게시판

참 오랜만에 쑥 나들이를 했더니...

이런... 하니비님 세미나 신청이 있었네요.

아이고... 아까버라...

당첨 되신 분들 모두 좋은 시간 가지세요~~

하니비님!!

떨지 마시구 좋은 말씀 많이 나눠주세요~~

운영자님!!

찍어서 올리는 센스!!!!

부탁 드려요~~

본론으로 들어가서...

하노이 탑을 아십니까?

아이 크리스마스 선물에 끼어 온 사은품입니다.

물론 아이는 별 관심도 없고

저만 좋아라 쪼그리고 앉아서 놀고 있으면 신랑은 무슨 병자 바라보듯 바라봅니다.

저런 식으로 크기 순서로 쌓아 올려진 원반들을 차근차근 옮기는 것입니다.

한번에 하나만, 큰 것 위에 작은 것을 옮겨 놓는 방식으로 8개의 원반을 다 옮기는데

옮기는 작업은 최소한 몇번 할 수 있을까요?

1 개는 1 번

2 개는 3 번 (맨 위의 작은 것을 옆으로 옮기고 큰 것을 다른 옆으로 옮긴후 작은 것을 큰 것 위로 옮김)

3 개는 7 번 (먼저 2개를 앞의 방법 대로 3번 만에 옮긴 후 제일 큰 원반을 옮겨 놓고 다시 두개를 큰 원반 위로 3번 만에 옮겨 놓습니다. 즉 3 + 1 + 3 = 7)

4개는 15 번 (먼저 3개를 앞의 방법 대로 7번 만에 옮겨 놓고 제일 큰 원반을 옮기고 3개를 큰 원반 위로 7번 만에 다시 옮겨 놓습니다. 즉 7 + 1 + 7 = 15 )

5개는 31 번 (4개를 앞의 방법 대로 15 만에 옮기고 가장 큰 원반 옮기고 다시 4개를 가장 큰 원반 위로 다시

15번 만에 옮겨놓습니다. 즉 15 + 1 + 15 = 31 )

그렇담 n+1개의 원반은 최소 몇번 만에 옮길 수 있을까요?

역시나 똑같습니다.

n개를 먼저 옮겨 놓고 가장 큰 것 옮기고 다시 n개를 옮기는 것입니다.

여기서 원반 갯수와 옮기는 최소 횟수 사이에 대응하는 기호를 만들어 보겠습니다.

n개를 옮기는 최소한의 횟수를 An이라 하면

n+1개를 옮기는 최소한의 횟수는 An+1( n+1 통째로 아래 첨자입니다)

An+1 = An + 1 + An

= 2An + 1

바로 점화식이 완성되었습니다.

점화식 漸化式

즉, 이웃한 두 항이 이루는 규칙을 보여주는 식이죠.

이 식을 요령껏 잘 풀어 내면 An = 2^n -1 이라는 일반항을 구할 수 있습니다 (2의 n 거듭 제곱입니다)

1개 ====> 2^1 - 1 = 1

2개 ====> 2^2 - 1 = 3

3개 ====> 2^3 - 1 = 7

4개 ====> 2^4 - 1 = 15

5개 ====> 2^5 - 1 = 31

127

255

.....................................

다 맞아 떨어지죠.

여기서 점화식을 통한 추론이 아닌 몇번의 경험으로 미루어 짐작할 수도 있습니다.

즉 1, 3, 7, 15, 31 ..... 이라는 결과를 가지고 계차 수열이라는 규칙을 발견해서 일반항을 찾아 낼 수도 있습니다만...

이럴 경우 점화식을 찾아 낼 수 없죠.

고2 수1에서서 배우는 점화식의 내용이지만 기본 개념은 어린 친구들도 이해할 수 있을 것 같습니다.

연속해서 일어나는 어떤 현상을 바라 보면서

결과만 가지고 다음을 예상하는 것 보다 그 사이 숨은 규칙을 발견해서 일반화 시킬 수 있는 힘이

진정한 수학적 능력이라고 생각합니다.

추상적인, 형이상학적인 과정이라서 누구나 쉽게 하는 것은 아닙니다.

그렇지만 실제 손으로 조작해보고 결과를 직접 경험해본다면

좀 더 쉽게 받아들일 수 있지 않을까요?

중학생, 고등학생도 이런 교구가 필요한 것 같습니다.

공부 이외엔 게임만 하는 아이들이 컴퓨터나 닌텐도 말고 다른 놀거리가 좀 있었음 좋겠습니다.

뭐가 좋을까요?

네비게이션

컨텐츠