점화식과 관련된 3문제의 풀이를 한번 적어본다.

퀴즈 386 5개의 구슬

5개의 구슬이 들어있는 주머니 A와 비어 있는 주머니 B 가 있다.

한번에 구슬을 한개 혹은 두개씩 뽑아 A 의 구슬을 B 로 옮기려고 한다.

총 경우의 수는?

hint : 이 문제는 쉽게 n 개의 구슬로 일반화가 가능하다. 한번에 구슬을 한개 혹은 두개씩 뽑아 이게 핵심 포인트이다. 사실 이 문제는 고등학교 때 빈번하게 등장했던 문제이다.

풀이

이 문제는 일일이 카운트 해봐도 되지만 일반화를 위해 고등학교 수학 지식을 사용해 보자. 바로 점화식을 이용한 풀이이다.

A 에 구슬이 n 개 있을 때 B 에 옮기는 경우의 수를 a_n (n>2, n=1, 2 이면 한번에 옮길 수 있기에 2보다 크다고 가정하자) 이라 하자. 문제의 조건에 따라 한번에 한개 혹은 두개를 옮길 수 있으니 이 전체를 두가지 조건으로 나누어 셀 수 있다.

하나는 A 에서 한개를 뽑아 B 에 두고 남은 (n-1) 개에서 B 로 가는 경우의 수 (즉 a_{n-1}) 그리고 다음은 A 에서 한번에 두개를 뽑아 B 에 두고 남은 (n-2) 개에서 B 로 가는 경우의 수 즉 a_{n-2} 가 된다.

이 수열은 우리에게 잘 알려진 수열이다. 바로 피보나치 수열. 처음 초항과 두번째 항은 쉽게 카운팅이 가능하다.

문제에서 원하는 답은 a_5 = 8 이다.

퀴즈 391 10자리의 홀수

0과 1 두 자리 숫자만 이용하여 만들 수 있는 10자리의 홀수인 자연수 중에서

0이 연속하여 나타나지 않는 자연수의 갯수를 구하여라

풀이

이 문제는 정확히 386번과 같은 문제이다. 이를 catch 할 수 있겠는가?

n 자리의 홀수의 개수를 a_n 이라 하자. n 자리를 만족하려면 먼저 n번째 자리는 0이 아니어야 하고 [여기는 0,1 즉 이진법만 고려했으니 n번째 자리에 1이 들어가야 한다.] 홀수라고 했으니 첫째 자리도 1이어야 한다. 자 이제 두번째 자리에 올 숫자를 생각하고 이를 점화식으로 연결해보자.

두번째 자리에는 0 또는 1이 올 수 있는데 먼저 0이 왔다고 해보자. 0이 연달아 올 수 없으니까 세번째 자리 숫자가 1로 고정된다. 즉 빈칸은 n-2 개가 있고 두번째, 세번째 숫자는 전체의 홀짝에 관여가 없으니 결국 a_{n-2} 와 같다. 반면 두번째 자리에 1이 온 경우는, 아무런 제한 조건이 없기 때문에 n-1 자리에 넣는 경우라고 보면 되고 a_{n-1} 이 된다.

원하는 숫자는 a_{10}, 앞에서 구한 수에 더 계산을 해보면 a_{10}=55 가 나온다 .

퀴즈 390 10계단

10계단을 올려가려고 한다.

한번에, 1계단, 2계단 혹은 3계단을 올라갈 수 있다고 할 때

10계단을 올라갈 수 있는 경우의 수는?

풀이

이 문제 역시 고등학교 참고서에 자주 등장하는 문제로, 위에 점화식을 구한 과정과 똑같은 방법으로 문제에 해당되는 점화식을 구할 수 있다.

n (n>3, n=1,2,3 일 때 한번에 올라갈 수 있으므로) 번째 계단을 오르는 방법을 a_n 이라 하자. 정확히 앞에 구한 방식과 똑같이 하면

참고로 여기서는 weight를 주지 않고 [항의 앞에 계수가 1인 경우만 고려했다.] 했는데 weight를 주는 문제를 모델링 할 수 도 있다. 아무튼 이런 식으로 점화식을 만들어 수열의 항을 구하는 문제가 학창시절에 종종 입시에 등장하곤 했는데 지금은 어떨지 궁금하다.