AMC 10 · 2019 · #23

학년 7 counting

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

combinations-basicrecursive-sequencepattern-recognitioncombinatorial-identitysystematic-enumeration caseworksystematic-enumeration ↑ 선수 지식: combinations-basicsystematic-enumeration

📏 중간 풀이 💡 3 개 인사이트

문제

0과 1로 이루어진 길이 19의 문자열 중에서 0으로 시작해 0으로 끝나고, 0이 연달아 두 번 나오지 않으며, 1이 연달아 세 번 나오지 않는 것이 몇 개인지 세세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #15 (다르게 정리): 한 칸씩 보지 말고 수열을 '0과 길이 1 또는 2 인 1-블록의 교차' 로 재구성 — 조건이 깔끔히 정리됨. 도구 #7 (쪼개기): (a) 0의 개수로 매개변수화, (b) 각 매개변수에서 이항계수로 배치 셈. 도구 #9 (더 쉬운 문제): 원 수열 셈을 단순 디오판토스 2k + s = 20 (음이 아닌 정수해)로 환원, 나열 쉬움. 도구 #2 (빠짐없이 나열): 가능한 (k, s) 각각에 C(k - 1, s) 적용.

1STEP 1

구조 파악하기

덩어리가 1 또는 11뿐입니다.

0 B₁ 0 B₂ 0 … B_k-1 0, B_i ∈ {1, 11}

2STEP 2

길이 방정식 세우기

전체 길이가 방정식 하나가 됩니다.

2k + s = 20, 0 ≤ s ≤ k - 1

3STEP 3

가능한 덩어리 수 찾기

가능한 개수는 네 가지입니다.

k ∈ {7, 8, 9, 10}

4STEP 4

각 경우 세기

어느 덩어리가 긴지 고르면 됩니다.

C(6, 6) + C(7, 4) + C(8, 2) + C(9, 0) = 1 + 35 + 28 + 1

5STEP 5

모두 더하기

네 값을 더합니다.

1 + 35 + 28 + 1 = 65

6STEP 6

답 읽기

합은 65입니다.

정답

양 끝 경우 검증. k = 7: 모든 분리 블록이 '11', 유일한 수열 0110110110110110110 — 길이 7 + 12 = 19 ✓, 0으로 끝 ✓. k = 10: 모든 분리 블록이 '1', 수열 0101010101010101010 — 길이 10 + 9 = 19 ✓. 양쪽 모두 조건 만족. 가운데 k = 8 (35 개), k = 9 (28 개)가 다수. 점화 f_n = f_n-2 + f_n-3의 초기 조건 설정에 주의 필요하므로 직접 이항계수 합산 (65)이 안전. 1 + 35 + 28 + 1 = 65 ✓.

💡핵심 정리

이 AMC 12 문제는 7학년 조합만 있으면 풀려요 — 각 수열을 '0 들 사이 1 또는 11 블록' 으로 보고 2k + s = 20 세움, k = 7, 8, 9, 10 각 C(k-1, s) 합 1 + 35 + 28 + 1 = 65.