한 쌍의 토끼가 있다.  암컷 토끼는 두 달이

지날 때부터 시작하여 매달 한 쌍의 토끼를 낳는다고

한다. 또 새로 태어난 암컷 토끼도 두 달이 지난 후

부터 시작하여 매달 한 쌍의 토끼를 낳는다고 가정하면

1년이 지난 후 전체 토끼의 수는 얼마인지 구하여 봅시다.

(단, 모든 토끼들은 계속 살아 있는다고 가정합시다. )

 중요한 점화수열인  Fibonacci 수열과 그 응용을학습한다.

       Fibonacci 수열과 그 응용

 

Fibonacci의 토끼문제. 한 쌍의 토끼가 있다. 암컷 토끼는 두 달이 지날 때부터 시작하여 매 달 한 쌍의 토끼를 낳는다고 한다. 또 새로 태어난 암컷 토끼도 두 달이 지난 후부터  시작하여 매달 한 쌍의 토끼를 낳는다고 가정하면 1년이 지난  후 전체 토끼의 수를 구하여 봅시다.  (단, 모든 토끼들은 계속 살아 있는다고 가정합시다. )

위의 문제는 1202년 르네상스 이전의 유럽 수학자로는 당대 최고의

학자인 이탈리아 수학자인 피보나찌 (G. Fibonacci)가 처음 제기한

문제로 생물학적인 문제라기보다는 정수론의 연습문제로 제기된 것으로

점화수열의 대표적인 문제로 알려져 있다.

이제 위 문제를 해결할 방법을 알아보도록 합시다.

먼저 R(n)을 n달이 지난 후의 전체 토끼의 쌍의 수를 나타낸다고

하자. 그러면

인 관계가 있음을 알 수 있다.  즉,

  R(0) = 1 (맨 처음의 토끼 1쌍)

R(1) = 1 (새로운 2세 토끼는 없다.)

R(2) = 2 (어미토끼 1쌍 ; 새끼토끼 1쌍)

R(3) = 3 (어미토끼 1쌍 ; 새끼토끼 2쌍)

………………………………………

 계속하여 R(n)의 항들을 써 보면,

                 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

 와 같음을 알 수 있다.

       이제 R(n)의 일반항을 구하는 방법은 이 후에 알아보도록 한다.

        먼저 다음의 예를 알아봅시다.

 

예제 1. 9개의 ＋ sign과 4개의 －sign을 한 줄로 나열하려고 한다. 이 때 어떤 두 개의 －sign도 인접하지 않아야 한다면, 가능한 나열방법은 몇 가지나 되겠는가?

풀이.  다음과 같은 상황을 생각하여 봅시다.

먼저  10 개의  x를 더하면,

그러면 ＋sign은 분명히 9개가 있다. 이 때 10 개의 x 중에서 4개를 골라서

x에 －를 대입한다고 생각하면, 우리가 구하는 나열의 모습이 될 수 있다.

따라서 구하는 나열의 방법의 수는

가지이다.     ?

위의 예를 일반적으로 기술하면 다음과 같다.

 

정리 1.  n개의 ＋부호와 k개의 －부호를 나열할 때 어떤 두 개의 －부호도 인접하지 않으려고 한다. 그러면 가능한 나열의 방법은 모두                    가지이다.

 

예제 2. 10개의 x가 나열되어 있다. 이 때 각각의 x를 ＋부호나 －부호로 교체하려고 하며, 어떤 두 개의 －부호도 인접하지 않게 하려고 한다. 그러면 가능한 경우는 몇 가지나 되는가 알아보시오.

풀이 . 먼저 다음과 같이 10 개의 x 가 나열되어 있다.

x  x  x  …  x

이 때, 아무 제한이 없이 x에 ＋부호와 －부호를 대입한다고 하면, 가능한

방법은 모두

2¹⁰

가지일 것이다. 그런데 －부호 2개는 인접하여서는 안되므로 가능한 방법은

일 경우이다.

따라서 앞의 정리 1에 의하여

이다.    ?

그런데,  앞의 피보나찌의 토끼문제에서

이며, 위 예제 2의 수 144는  단순한 우연은 아님을 나중에 알 수 있다.

이제 위의 ＋부호와 －부호의 나열 문제를 일반적으로

생각하여 봅시다.

＋부호와 －부호의 n개 나열을 n-수열이라고 하자. 어떤 두 개의

－부호도  인접하지 않도록 ＋부호와 －부호를 n개 나열하는 방법의

수를

이라고 하자. 그러면

 

이제 B(n) 의 일반항을 구하는 방법을 알아보도록 하자.

n-수열을 생각할 때, 먼저 ＋부호가 맨 처음이면 이후의 (n-1)수열은

B(n-1)가지로 나타날 수 있다.

그러나, 맨 처음의 부호가 －인 경우는 그 다음은 －부호가 되어서는

안 되며, (왜냐하면, 두 개의 －는 인접하여서는 안된다.) 따라서, 반드시

＋부호가 나와야 하며, 따라서 가능한 방법은 B(n-2)가지가 될 것이다.

따라서 구하는 방법은

이며, 이것은 피보나찌 수열의 점화식과 일치한다.

실제로

과 같으며,

이다. 

 

정리 2.  B(n) 과 R(n) 의 관계식은 다음과 같다.

 

문제 1.  10개의 계단을 올라가려고 한다. 이 때, 계단을 한 계단 또는 두 계단씩 올라갈 수 있다고 한다면 가능한 방법은 모두 몇 가지인가 알아보아라.

 

문제 2. 10개의 ＋부호와 9개의 －부호가 있다. 다음의 경우에 이들을 나열하는 방법에 대하여 알아보아라.   ⑴ 아무 제한이 없을 경우 ⑵ 어떤 두 개의 ＋부호도 인접하지 않을 경우 ⑶ 어떤 두 개의 －부호도 인접하지 않고 어떤 두 개의 ＋부호도 인접하지 않을 경우

 

문제 3. 8자리의 이진법 수 중에서 00 이 나타나지 않는 수의 개수는?

   앞의 예에서 학습하였던 바와 같이 B(n)을 구할 수 있는 구체

적인 식을 알 수 있다.   즉,

 이 때

이고   [x]는  x의 가우스 함수값이다.

즉,   n = 10 인 경우는

이다.

 

정리 3. 피보나찌 수 R(n) 은 다음과 같이 구할 수 있다.

  피보나찌 수에 관하여는 표준적인 정수론의 교과서 (예를 들면,

김응태,박승안저, 정수론, 경문사, 1997 등)를 참고하기

바라며, 피보나찌 수에 관한 여러 가지 구체적인 점화 관계식을

얻을 수 있다.

예를 들면, 다음과 같은 점화 관계를 얻을 수 있다.

다음의 그림에서와 같이 Fibonacci 수와 이항계수 사이에는 놀라운 관계가 있음을 주의하도록 합시다.

Fibonacci Numbers and Binomial Coefficients. The fibonacci numbers appear unexpectedly in Pascal's triangle, when viewed from the right angle(see Figure 3). Prove that

   중요한 점화수열인  Fibonacci 수열을 여러 나열의 문제와

관련하여  학습하였고, 그의 중요한 여러 성질에 관하여

학습하였다.

 다음 방정식을 만족하는 자연수 해 (x,y,z) 는 모두 몇 개인가

구하시오.

              x + y + z = 5

  세기의 방법을 활용하여 대표적 부정방정식인

 선형 Diophantine 방정식에 대하여 학습한다.

 선형 Diophantine 방정식

주어진 정수 a, b, n 에 대하여  이원일차방정식

                ax + by = n

을 만족하는 정수  x, y 를   구하는 문제는 여러 가지 풀이

방법을 생각할 수 있다.  본 강의에서는 앞에서 학습한

세기의 방법을 활용하여 구하도록 한다.

일반적으로 위와 같이 정수계수의 대수방정식의  정수해를

구하는 문제를 부정방정식  또는  Diophantine 방정식

이라고 한다.  이에 관하여는 정수론책을 참고하기

바랍니다.

 

먼저 다음의 예를 생각하여 봅시다.

 

예제 1. 방정식 x + y + z = 6 을 만족하는 양의 정수해는 모두 몇 개인가?

풀이. 방정식이 해를 순서쌍  (x,y,z) 라고 표시하면, 구하는 해는

(4, 1, 1), (3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 2, 2),

(2, 1, 3), (1, 4, 1), (1, 3, 2), (1, 2, 3), (1, 1, 4)

의 모두 10개가 있다.     ?

위의 예제를 풀기 위하여 다음과 같은 방법을 생각하여

봅시다.

먼저 6 을 다음과 같이 표현하면

 1 + 1 + 1 + 1 + 1 + 1 = 6

이제 양의 정수해 ( x , y , z ) 를 구하기 위하여는 위의 표현에서

2개의 ＋부호를 선택하면 된다. 즉,

와  같이 골랐다면,

( x , y , z ) = (2 , 3 , 1 )

로 생각할 수 있다. 따라서 구하는 해의 개수는

개 이다.     ?

 

정리 1. 자연수  m 에 대하여   에서 모든 xi 가 양의 정수인 해의 개수는   개이다.

증명.앞의 방법에서와 같이 ( m - 1 ) 개의 ＋ 부호 중에서 ( n - 1 )

개의 ＋ 부호를 고르는 방법의 수이다.    ?

 

예제 2.  x + y + z + w = 15를 만족하는 양의 정수해 (x,y,z,w) 의 개수는 모두 몇 개인가?

풀이.

  ?

 

문제 1.  x + y + z + w = 13을 만족하는 양의 정수해 (x,y,z,w) 의 개수는 모두 몇 개인가?

    앞의 예제 1에서 조건을 약간 바꾸어 생각한다.

예를 들어, 방정식 에서 음이 아닌 정수해 의 개수를 구하여 봅시다.

그러면 5 개의 1 과 2 개의 ＋부호를 나열하여 구할 수 있다. 즉,  

은

로 생각하고,

은

로 생각할 수 있다.

즉, 두 개의 ＋로 를 구별할 수 있으므로, 가능한 방법의 수는 5 개의 1 과

2 개의 ＋부호를 나열하는 방법의 수

개이다.

    따라서 다음의 정리를 얻을 수 있다.

 

정리 2.   자연수 m 에 대하여 방정식 에서 모든 xi 가 음이 아닌 정수인 해의 개수는   이다.

증명. m 개의 1 과  ( n - 1 ) 개의 ＋ 부호를 나열하는 방법의

개수이므로

   ?

 

예제 3.     x + y + z + w = 15를 만족하는 음이 아닌 정수해  (x,y,z,w) 의 개수는 모두 몇 개인가?

풀이. 구하는 해의 개수는  

  ?

  x + y + z = 16  의 정수해 중에서  x, y, z 가

모두  2 보다 큰 경우의 정수해의 개수를 구하여 봅시다.

먼저 방정식의 미지수를 바꾸어

라고 두면,  q , r , s 는 모두 양의 정수가 된다. 그러면

   따라서  x + y + z = 16 이고  x, y, z  가 모두  2 보다 큰

정수해를   구하는 문제는 q + r + s = 10  이고  q , r , s 가

모두 0보다 큰  정수 ( 자연수 ) 해 를 구하는 문제로 바뀌었다.   따라서

정리 1 에 의하여 구하는 해의 개수는

이다.

 

예제 4. 다음 조건을 만족하는 Diophantine 방정식의 해의 개수를 구하시오.

풀이. 주어진 방정식의 미지수를 다음과 같이 바꾼다.

 그러면,  q, r, s, t 모두 자연수가 된다.

 이 들을 원 방정식에 대입하여 정리하면

따라서  q + r + s +t = 17 을 만족하는 자연수해 의 개수를

구하는 문제이므로,  정리 1에 의하여

  ?

 

문제 2. 예제 4 의 문제를 정리 2 를 이용하여 해결하여 보시오.

 

문제 3. 다음 제한조건을 만족하는 정수해의 개수를 각각 구하시오.

 세기의 방법을 활용하여 대표적 부정방정식인

 선형 Diophantine 방정식에 대하여 학습하였다.