AMC 10 · 2015 · #22

학년 9 countingpattern

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

recursive-sequencemodular-arithmeticchinese-remainder-theorem pattern-recognitionidentify-subproblems ↑ 선수 지식: recursive-sequencemodular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

두 기호로 된 긴 문자열에서 한 기호가 연달아 네 번 나올 수 없다. 그 개수의 나머지를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

도구 #7(작은 문제로 쪼개기)이 핵심 엔진입니다. 올바른 문자열은 같은 글자 1 개, 2 개, 또는 3 개로 된 덩어리로 끝나고, 그 덩어리를 잘라내면 더 짧은 올바른 문자열이 남으므로, 거대한 하나의 세기가 같은 종류의 작은 세기 셋으로 바뀝니다. 도구 #16(관점 바꾸기)은 먼저 '전체를 센다'를 'A 로 끝나는 것만 센다'로 바꾸는데, A⇔ B 대칭 덕분에 그것이 정확히 전체의 절반입니다. 도구 #9(더 쉬운 문제로 줄이기)는 'S(2015)가 얼마인가'라는 불가능한 질문을 '나머지가 얼마인가'라는 작은 질문으로 바꾸고, 그 답에 필요한 정밀도가 어디까지인지 정확히 짚어 줍니다. 도구 #11(거꾸로 풀기)은 점화식을 거꾸로 돌려 index 0의 값을 정당하게 정하고, 덕분에 뒤의 index 계산이 어긋나지 않습니다. 도구 #5(패턴 찾기)로 모든 항을 2와 3으로 나눈 나머지로 줄이면 각각 4 항, 13 항마다 반복됩니다. 그다음 도구 #3(가능성 지우기)으로 6으로 나눈 나머지 여섯 개를 훑어 살아남는 하나만 남깁니다.

1STEP 1

마지막 글자로 나누기

대칭이 두 끝맺음을 같게 만든다.

S(n)=A(n)+B(n)이고 A⇔ B 바꾸기에서 A(n)=B(n) 이므로 S(n)=2A(n)

2STEP 2

마지막 덩어리 떼어내기

마지막 덩어리를 떼면 점화식이 나온다.

n ≥ 4 일 때 A(n)=B(n-1)+B(n-2)+B(n-3)

3STEP 3

하나의 수열로 바꾸기

그것이 하나의 수열로 닫힌다.

A(n)=A(n-1)+A(n-2)+A(n-3) (n ≥ 4)

4STEP 4

출발 값 정하기

출발 값은 손으로 정한다.

A(0)=1, A(1)=1, A(2)=2, A(3)=4, A(4)=7, A(5)=13, A(6)=24,…

5STEP 5

필요한 정밀도 정하기

작은 나머지만 따라가면 된다.

A=6q+r → S=2A=12q+2r → S≡ 2r (mod 12)

6STEP 6

2로 나눈 나머지: 주기 4

한 법에서는 네 항마다 반복된다.

A(n) mod 2: 1,1,0,0 | 1,1,0,0 |… 이고 2015=4 · 503+3 이므로 A(2015)≡ A(3)≡ 0 (mod 2)

7STEP 7

3으로 나눈 나머지: 주기 13

다른 법에서는 열세 항마다 반복된다.

2015=13 · 155 → A(2015)≡ A(0)=1 (mod 3)

8STEP 8

6으로 나눈 나머지 하나로 합치기

둘을 합치면 나머지 하나가 정해진다.

A(2015)≡ 0 (mod 2)이고 ≡ 1 (mod 3) → A(2015)≡ 4 (mod 6)

9STEP 9

두 배 하고 나머지 읽기

두 배 하면 8, 보기 (D).

S(2015)≡ 2 · 4=8 (mod 12) → (D)

정답

직접 셀 수 있을 만큼 짧은 길이에서 장치를 시험해 봅니다. 길이 3 이하의 문자열은 모두 올바르므로 S(1)=2, S(2)=4, S(3)=8입니다. 길이 4 에서는 문자열이 16 개이고 올바르지 않은 것은 AAAA 와 BBBB 둘뿐이므로 S(4)=14 인데, 8+4+2=14로 점화식과 맞습니다. 계속하면 S(5)=26, S(6)=48, S(7)=88이고 직접 나열해도 같습니다. index 계산도 두 갈래로 확인됩니다. 6으로 나눈 나머지에서 수열 A(n)의 주기는 lcm(4,13)=52이고 2015=52 · 38+39 이므로 A(2015)≡ A(39) 인데, 이것도 ≡ 4 (mod 6)으로 2와 3을 따로 다룬 결과와 같습니다. 끝으로 올바른 문자열은 A⇔ B 바꾸기로 짝을 이루므로 S(n)은 언제나 짝수이고, 짝수 나머지가 나오는 것은 예상된 일입니다. 선택지가 모두 짝수라 그것만으로는 결정되지 않으며, 6까지 정확히 따진 계산이 8, 즉 선택지 (D)를 골라 줍니다.

💡핵심 정리

문자열이 어떻게 끝나는지로 나눠 세고, 그것을 앞 세 항을 더하는 규칙으로 바꾼 다음, 나머지만 추적하세요. 나머지는 짧은 주기로 돌고 그 위의 자리를 정확히 짚을 수 있습니다.

마지막 글자로 나누기
마지막 덩어리 떼어내기
하나의 수열로 바꾸기
출발 값 정하기
필요한 정밀도 정하기
2로 나눈 나머지: 주기 4
3으로 나눈 나머지: 주기 13
6으로 나눈 나머지 하나로 합치기
두 배 하고 나머지 읽기