수학의 재미2019 AMC 12B 문제23 재귀수열

(문제)
0 으로 시작해서 0 으로 끝나는, 0 과 1 만 으로 이루어진
19자리 수는   몇개인가?
단, 연속된 2개의 0 이나, 연속된 3개의 1 은 허용되지 않는다.

(풀이 1)
주어진 조건으로부터, 유효한  n  자리수는 0 다음에 1 0 이나 1 1 0 이 올수있다.
그래서, 재귀함수 f(n) = f(n - 3) + f(n - 2) 을 정의 할수있다.
여기서, f(n)은 유효한 n 자리수의 개수다.
왜냐하면 유효한 n  자리수에, 1 0 이나 1 1 0 을 더 추가하여 주어진 조건을 만족하는 수를 만들수 있기 때문이다.

f(3) = 010 = 1
f(4) = 0110 = 1
f(5) = 01010 = 1
f(6) = 010110, 011010 = 2
f(7) = 0110110, 0101010 = 2
f(8) = 01010110, 01011010, 01101010 = 3
f(9) = 010101010, 011010110, 010110110, 011011010 = 4

f(10) = f(7) + f(8) =2 + 3 = 5
f(11) = f(8) + f(9) = 3 + 4 = 7
f(12) = 4 + 5 = 9
f(13) = 12
f(14) = 16
f(15) = 21
f(16) = 28
f(17) = 37
f(18) = 49
f(19) = f(16) + f(17) = 28 + 37 = 65

답은 f(19) =  ( C) 65

(풀이 2)
0 이 나온후, 다음 0 은 2칸 이나 3칸 아래에 올수있다.
 제일 앞자리 0 부터, 마지막 19번째 자리 0 까지 18칸을 채운다.
그래서, 18칸을 2s ( 10  )  이나 3s ( 1 1 0  )  로 채운다.
다음과 같이 몇가지 방식이 가능하다.

Case 1: 9개의 2s ( 10  )  : 1 가지
          0101010101010101010

Case 2: 2개의 3s ( 1 1 0  ) 6개의 2s ( 10  ) : 28 가지
          모두 8 개 자리에서 2개를 선택 하면되니 8C2 = 28
          2S (3S) 2S 2S 2S (3S) 2S 2S

Case 3: 4개의 3s ( 1 1 0  ) 3개의 2s ( 10  ) : 35 가지
           7C3 = 35
           (2S) 3S 3S (2S) 3S (2S) 3S

Case 4: 6개의 3s ( 1 1 0  ) : 1 가지

           0110110110110110110

4 경우를 모두 더하면 1 + 28 + 35 + 1 = 65
(C) 65 가 답이다.

How many sequences of 0s and 1s of length 19 are there that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s?
(A) 55  (B) 60 (C) 65 (D) 70 (E) 75

Solution 1 (recursion)

We can deduce, from the given restrictions, that any valid sequence of length  will start with a  followed by either  or . Thus we can define a recursive function , where  is the number of valid sequences of length .

This is because for any valid sequence of length , you can append either  or  and the resulting sequence will still satisfy the given conditions.

It is easy to find  and  by hand, and then by the recursive formula, we have .

Solution 2 (casework)

After any particular , the next  in the sequence must appear exactly  or  positions down the line. In this case, we start at position  and end at position , i.e. we move a total of  positions down the line. Therefore, we must add a series of s and s to get . There are a number of ways to do this:

Case 1: nine s - there is only  way to arrange them.

Case 2: two s and six s - there are  ways to arrange them.

Case 3: four s and three s - there are  ways to arrange them.

Case 4: six s - there is only  way to arrange them.

Summing the four cases gives .

궁금한게 있거나, 모르는 부분이 있으면 연락 바랍니다.
010-3549-5206 으로 전화 주시면 됩니다.
말로 설명하면 5분이면 충분한데, 글로 쓰면 몇시간 작업이 필요합니다. 
그래도 미국수학경시문제(AMC8/10/12 , AIME) 소개할려고 합니다.
영어로 바로 문제 이해하고 풀수있는 학생도 있겠지만,
그렇지 못하지만, 수학을 사랑하는 사람들을 위해 문제를 번역하고 
설명 해설을 덧붙여서, 누구든지  수학의 재미를 느낄수 있기를 바라면서
힘들어도 계속 필요한 문제를 찾아 소개 하고자 합니다.
많은 성원 바랍니다.