동판에 막대가 세 개 있고, 크기가 서로 다른 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 억년 미만이므로, 이 세상은 연기처럼 사라질 것이다라는

이야기는 과학적으로 증명할 수 있는 사실이기도 하다. (우리가 여러 가지

역사적 사실에서 알 수 있듯이, 예전의 우리 선조들은 놀랍도록 과학적이다 !)

 그러면 위의 하노이탑 문제는 어떻게 해결할 수 있는가 알아보도록

하자. 먼저 하노이탑 문제를 일반적으로 기술하면 다음과 같다.

 

하노이탑 문제 (Hanoi Tower Problem)   동판에 막대가 세 개 있고, 크기가 서로 다른 n 개의 원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다.   (1) 한 번에 한 개의 원판만을 옮긴다. (2) 크기가 큰 원판은 반드시 크기가 작은 원판      아래쪽에 있어야 한다.   그러면 원판을 모두 다른 막대로 옮기는데 필요한 이동 (move) 회수는 모두 몇 번 인가 알아보시오.

 

 

이러한 문제는 전형적인 귀납적사고를 필요로

하는 문제이다. 즉, 특별한 몇 가지의 경우를

관찰하여 일반적으로 적용할 수 있는 규칙을

      추론하고 이를 엄밀하게 수학적으로 증명하는

      과정을 거쳐 문제를 해결하도록 합시다.

먼저 원판이 한 개 뿐이라면, 우리가 필요한 원판의 이동회수는 1회 이다.

이제 원판이 두 개 뿐이면, 우리는 다음 그림과 같은 단계로 원판을 움직일

수 있다.

따라서 필요한 원판의 이동회수는 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장의 원판들이 차례로 크기 순으로 계속하여 2n 개가 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다.   (1) 한 번에 한 개의 원판만을 옮긴다. (2) 크기가 큰 원판은 반드시 크기가 작은 원판      아래쪽에 있어야 한다. (3) 같은 크기의 2장의 원판은 똑같은 것으로 생각한다.   그러면 원판을 모두 다른 막대로 옮기는데 필요한 최소 이동 (move) 회수는 모두 몇 번 인가 알아보시오.

위 문제는 하노이탑 문제를 일반화할 수 있는 여러 방법 중 가장

간단한 모양이다. 문제의 가정에서 같은 크기의 2장의 원판은 똑같은 것으로

생각한다고 하였으므로, 2개의 같은 크기의 원판을 계속하여 같은 막대로

옮긴다고 가정하면, 이는 2개의 원판을 한꺼번에 움직인다고 생각하여

계산하여도 될 것이다.

따라서, 우리는 일반화된 하노이탑 문제에서 2n개의 원판이 있을 때 모두

옮기는데 필요한 원판의 이동회수를 A(2n)이라고 하면, 관계식

을  짐작할 수 있다.

 

문제 3. 일반화된 하노이탑 문제에서 같은 크기의 2장의 원판이 서로 다르다고  가정한다면 2n 개의 원판을 모두 옮기는데 필요한 원판의 이동회수 B(2n)은 얼마인가 알아보시오.

위의 상황을 더욱 일반화하면 다음과 같이 생각할 수 있다.

크기 k 인 원판은 n_k개이고, m 개의 서로 다른 크기를 갖는 일반화된 하노이

탑의 경우 총   n₁⁺ n₂ ^{+... +} n_k 개의 원판을 모두 옮기는데 필요한

원판의 이동회수   A ( n_1,n_2,..., n_k) 는 얼마인가 등 여러 가지

다양한 일반화를 생각할 수 있다.

이에 관하여는 참고문헌[ Knuth and et-al.]에 있는 Knuth의 책을 참고 하기 바랍니다.

이제 위의 귀납적사고와 관련된 다음 문제를 알아봅시다.

 

평면에 n 개의 직선을 그려서 분할된 평면의 영역의 개수는 몇 개인가 알아보시오. ( 단, 임의의 두 직선은 항상 한 점에서 만나고, 임의의 세 직선은 동일한 점에서 만나지 않는다고 가정한다. )

위의 문제도 하노이탑 문제와 같이 귀납적사고 (inductive reasoning)

을  통하여 해결할 수 있다. 즉, 특별한 몇 경우에 대하여 차례대로 구체적

모습을 구하고, 그 곳에서 일반적인 관계를 유도하는 사고법을 따라서 문제를

해결하여 봅시다.

먼저 직선의 개수 n에 대하여 분할된 평면의 영역의 개수를 A(n) 이라

두면,

 

n = 1 이면  A(1) = 2   (개)

n = 2 이면  A(2) = 2 + 2 = 4

n = 3 이면  A(3) = 2 + 2 + 3 = 7

n = 4 이면  A(4) = 2 + 2 + 3 + 4 = 11

......

위 그림에서 ●은 새로 생긴 영역을 나타낸다. 따라서 위의 그림으로

부터 우리는 다음과 같은 점화식을 얻을 수 있다.

A(n) = A(n-1) + n   ( n은 2 이상인 자연수)

     A(1) = 2

따라서

 이다.

 

문제 3.  n =5 인 경우, 생기는 평면의 영역의 개수를 실제로그림을 그려서 확인하여 보시오.

 

문제 4. 다음 그림과 같이 계란모양의 곡선 (oval)이 만나서 생기는 평면의 영역의 수를 알아보려고 한다. 평면에 n 개의 계란모양의 곡선을 그려서 분할된 평면의 영역의 개수는 몇 개인가 알아보시오. 단, 임의의 두 계란모양의 곡선은 항상 두 점에서 만나고, 임의의 세 개의 계란모양의 곡선은 동일한 한 점에서는 만나지 않는다고 가정한다.

 

본 강의에서는 하노이탑 문제를 해결하고 그 일반화를

학습하는 과정을 통하여 수학 문제 풀이에서 귀납적

사고의 중요성을 강조하였다.

 

 가로 세로의 간격이 각각 1 씩인 점들로  구성된

격자평면 (lattice plane)위에 두 점을 임의로 택한다.

 이 때, 두 점을 잇는 선분을 그리고, 그 선분 위에

격자점이 있는 경우와 없는 경우를 각각 생각하여 보고,

어떤 조건이 두 경우를 규정할 수 있는가 알아보시오.

 

 본 강의에서는 격자평면 위의 여러 점들의 상황을

정수가 갖는 성질을 이용하여 해결하는 방법에 관하여

알아본다.  또, 이러한 방법을 통하여 수학문제 해결의

방법으로 다양한 기하적 방법과 대수적 방법을 생각하여

본다.

        격자다각형(lattice polygon)의 문제

     지난 강좌의 하노이탑 문제에 이어서 마지막으로

이산수학에서 전형적인 예를 알아봅시다. 

다음과 같이 평면 위에 가로 세로의 간격이 각각 1 씩인

점들로  구성된 격자평면 (lattice plane)을 생각하여 봅시다.

이 때, 아래의 그림에서와 같이 원점 O에서 주위를 바라

보았을 때,  곧바로 보이는 점 (예를 들면, 점 P와 같은 점)을

visible point 라고 하고, 다른 점에 가로 막혀서 보이지 않는

점 (예를 들면, 점 Q와 같은 점)을 invisible point라고 한다.

   그러면 어떤 점이 visible point이고, 어떤 점이 invisible

point인가를 결정하는 문제를 알아보도록 합시다.

먼저 invisible point Q(m,n)은 원점 O와 점 Q를 잇는 선분 OQ

위에 분명히 가로 막는 격자점 Q'(m',n')이 있다. 따라서, 점 Q의 x, y

좌표 m, n 은 각각 점 Q'의 좌표 m', n'의 배수임이 분명하다. 즉, m 과

n의 최대공약수 d는 1 보다 큰 수이며, 서로 소가 아님이 분명하다.

반면에, visible point P(m,n)인 경우에는 중간에 가로 막힌 점이

없으므로 ,점 P 의  x , y 좌표 m, n은 어떤 격자점의 좌표의 배수가

되어서는 안된다. 따라서, m 과 n의 최대공약수 d는 1 이며, 두 수 m, n

은 서로 소 이다.

 

예제 1. 점 P(17, 23)과 Q(26,46)은 각각 visible point 인가를 결정하시오.

  풀이. 점 P의 최대공약수 gcd( 17 , 23 ) = 1  이므로, 점 P는

visible point 이다.  또,

점 Q의 최대공약수   gcd ( 26 , 46 ) = 2 이므로,

점 Q  는  invisible point이다.  즉,  점 Q'( 13 , 23 )이

점  Q를 가로 막고 있다.   ?

     이제 위의 문제를 일반화하여 두 점 P(m, n), Q(r, s)가

서로 바라 볼 수 있는가를 결정하여 봅시다.

우리는 위 문제에서 평행이동을 사용하면 앞의 문제로 바꾸어 생각할 수

있다.  즉, 점 P를 원점 O로 평행이동하면, 점 Q는 Q'(r - m, s - n)

으로 평행 이동이 됨을 알 수 있다. 따라서, 우리는 두 수 r - m, s - n 이

서로 소인가 아닌가를 판정하면 충분하다. 이 때, 서로 바라볼 수 있는

점들을 mutually visible points(서로 바라볼 수 있는 점들)

라고 부른다.   즉, 다음 그림에서 두 점  P와  Q는 mutually visible

points이다.

 

예제 2. 점 P(26, 13)과 Q(5, 5)는 서로 바라볼 수 있는 가를  결정하시오.

풀이. 점 Q를 원점으로 평행이동하면, 점 P는 새로운 점

P'(26 - 5, 13 - 5) = (16, 8)

이 된다. 따라서, x, y 좌표의 최대공약수d = (16, 8) = 8 이므로 서로

바라볼 수 없다.  즉, 중간에 어떤 다른 격자점이 놓여 있다.    ?

 

문제 1. (1)점 P(17,23 ) 과 Q( 5 , 7 )은  서로 바라볼 수 있는가를 결정하시오. (2) 점 P(14, 26 ) 과 Q( 6 , 8 )은 서로 바라볼 수 있는가를 결정하시오.

 

문제 2.  격자평면 위에서 원점 O를 지나는 직선 y = 3x 를  그리고, 직선 위에 있는 격자점들의 x, y 좌표들의 관계를 알아보시오.

격자평면 위에서 원점 O를 지나는 직선을 생각하여 보자.

직선은 기울기에 따라서 여러 가지 모양으로 변할 수 있다.

이 때, 원점 이외의 어떤 격자점도 지나지 않는 직선이 존재할

수 있는가를 생각하여 봅시다.

우리는 이 문제의 해결의 실마리를 어디부터 찾아야할까요 ?

몇 번의 걸쳐서  직선을 그려보고  해결의 열쇠를 구하도록 합시다.

우선 우리가 관찰한 바에 의하면, 직선에서 가장 중요한 data는 기울기임을

알 수 있다. 만약 직선 이 원점 이외의 격자점 P(m,n)을 지난다면,

직선의 기울기는 유리수

이다. 따라서

와 같이 무리수 기울기를 갖는 직선은 원점 이외의 격자점을 지날 수 없다.

이와 같은 사고방법을 귀류법적 사고방법이라고 하며, 많은 (수학)문제들이

귀류법을 사용하여 해결될 수 있다.

 

문제 3.  소수(prime number)의 개수는 무한히 많음을                      증명하시오.

위 문제는 정수론에서 Euclid의 증명으로 알려진 유명한 귀류법

(연역법과 반대인 증명법)을 사용하는 증명이다.

 

문제 4.격자평면 위에서 원점 O와 다른 한 점 Q 만을 지나는 지나는 직선은 존재하는가 알아보시오.

  

앞에서와 같이 위 문제는 보다 높은 차원 ( 3차원, 4차원 등 ) 으로

일반화 할 수 있다.  이에 대하여 각자 연구하여 보시오.

 이제 위 문제의 응용문제로 다음과 같은 상황을 생각하여

봅시다.

  

문제 5. 다음 수를 구체적으로 간단히 계산하여 보시오.     단, [x] 는 x를 넘지 않는 최대의 정수 (Gaussian                    Integer Function)를 나타낸다.

풀이.

이와 같이 계산하여서는 문제를 해결할 수 있는 일반적인 관계식을

추측하기 어렵다.

 이제 주어진 식을 관찰하여 보면, 다음 그림에서 볼 수 있듯이

격자평면 위의 직선

와 밀접한 관계가 있음을 알 수 있다. 즉, 우리의 문제는 x 축 위에

있으며 직선 아래에 있는 격자점의 개수를 구하는 문제로 바꾸어 생각할 수

있다. 따라서 가장 중요한 요소는 직선

위에 과연 격자점이 있는가의 확인이다. 그런데 기울기

에서 17 과23은 서로 소이므로 직선 위에는 어떤 격자점도 없음을 알 수

있다. ( 왜냐하면, 만약 어떤 격자점이 있다면 17  과 23 은 각각 그 좌표의

배수이므로 서로 소가 될 수 없다 ! )

따라서 우리가 구하는 격자점의 개수는 전체 직사각형 안의 격자점의

개수의  반에 해당하므로,

이다.      ?

 

문제 6. a와 b가 서로 소인 자연수일 때, 다음을 간단히          계산하시오.             단, [x] 는 x를 넘지 않는 최대의 정수 (Gaussian          Integer Function)를 나타낸다.

이와 같이 문제해결 (problem solving)를 할 때, 그림을

사용하여 문제해결의 실마리를 풀어가는 것은 대표적인

탐구방법 (heuristic method ) 이다.

이제 위 문제와 관련된 확률에 관한 다음의 문제를

생각하여 봅시다.

 

문제 7 .격자평면 위에서 한 점을 임의로 택할 때, 그 점이 visible point (즉, 원점 O 에서 보이는 점)일 확률은 어느 정도가 되는지 알아보시오.

풀이. 이 문제는 앞에서 생각한 문제와 같이 기울기에 관한 사고를 통하여

해결할 수 있다. 즉, 임의로 고른 한 점을 P(m,n)이라고 하면, 두 수 m,

n이 서로 소가 되어야 P점이 visible point가 된다.  따라서, 위 문제는

자연수 에서 두 수 m과 n을 임의로 선택할 때 서로 소가 될 확률을 구하는

문제가 된다. 이 것은 약간 복잡한 계산이 필요하지만 다음과 같이 그 풀이를

소개 한다 :

     Let g be the greatest common divisor of

two integers a and b,that is g = (a,b) and let p be the

probability* that  g = 1.  We will first show that the probability

that  g = n for n = 1,2,... is  p/n^{2 .}

  Clearly the probability that n divides both a and b is ¹/n^{2 .}

  The probability that no proper multitple of n divides both a

and b is the same as the probability that (a/n, b/n) = 1,

which is p. Thus, the probability that g = n is p/n^{2 .}

  The sum of the probabilityes that g = n  for n = 1, 2, ...  must equal 1, so that

Solving for p, we obtain

*The probability is defined by

   ?

위 문제를 활용하여 다음을 구하여 보시오.

 

문제 8. 격자평면 위에서 두 점을 임의로 택할 때, 그 점이 서로 보일 (mutually visible points) 확률은 얼마인가 알아 보시오.

위에서 학습한 바와 같이 많은 그림이나  도형에 관한 수학문제들은

대수적 또는 기하적인  여러 방법에 의하여 해결할 수 있는 방법이

있음을 알 수 있다.

 

문제 9.  정사각형 ABCD 안에 임의의 한 점 P를 택하여 만들어진 삼각형 ABP가 예각삼각형이 될 확률은 얼마인가 알아보시오.

 

본 강의에서는 격자평면 위의 여러 점들의 상황을

정수의 성질로 이해하여 해결하는 방법에 관하여 알아

보았다.  또, 이러한 방법을 통하여 수학문제 해결의

방법으로 다양한 기하적 방법과 대수적 방법을 생각하여

보았다.