AMC 10 · 2019 · #25

학년 7 counting

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

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

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

문제

0 으로 시작·0 으로 끝나고, 0 이 연속 두 번 없고, 1 이 연속 세 번 없는 길이 19 의 0, 1 수열의 개수는?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

0 으로 시작·끝, 00 없음 → 0 들을 블록 B_i ∈ {1, 11} 로 분리한 꼴, k 는 0 의 개수.

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

2STEP 2

k - 1 개 분리 블록 중 '11' 블록 수 s 로 두면, 총 길이 조건 2k + s - 1 = 19 에서 2k + s = 20.

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

3STEP 3

s = 20 - 2k 에서 s ≥ 0, s ≤ k - 1 조건이 k ∈ {7, 8, 9, 10} 으로 좁혀요.

k ∈ {7, 8, 9, 10}

4STEP 4

각 k 에서 '11' 자리 선택 수 C(k-1, s): k = 7, 8, 9, 10 에 대해 1, 35, 28, 1.

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

5STEP 5

네 경우 합: 1 + 35 + 28 + 1 = 65 — 선택지 (C).

1 + 35 + 28 + 1 = 65

6STEP 6

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

비슷한 유형 더 풀어보기