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 개 인사이트

문제

How many sequences of $0$ s and $1$ s of length $19$ are there that begin with a $0$ , end with a $0$ , contain no two consecutive $0$ s, and contain no three consecutive $1$ s?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $0$ 으로 시작·$0$ 으로 끝나고, $0$ 이 연속 두 번 없고, $1$ 이 연속 세 번 없는 길이 $19$ 의 $0, 1$ 수열의 개수는?

주어진 것: 길이 $= 19$; 문자 $\{0, 1\}$; $0$ 으로 시작, $0$ 으로 끝; $00$ 부분수열 없음; $111$ 부분수열 없음; 선택지: (A) $55$, (B) $60$, (C) $65$, (D) $70$, (E) $75$

구하는 것: 모든 조건을 만족하는 수열의 개수

이해

문제 재정리: $0$ 으로 시작·$0$ 으로 끝나고, $0$ 이 연속 두 번 없고, $1$ 이 연속 세 번 없는 길이 $19$ 의 $0, 1$ 수열의 개수는?

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기, #15 다르게 정리하기

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

실행 — 정답: C

#15 다르게 정리하기 4.OA.C.5 단계 1

수열 재구성.
$0$ 으로 시작·끝, $00$ 없음 → $0$ 들이 한 개 또는 두 개의 $1$ 로 분리.
$0 \, B_1 \, 0 \, B_2 \, 0 \, \ldots \, B_{k-1} \, 0$ 꼴, $k$ 는 $0$ 의 개수, 각 $B_i \in \{1, 11\}$.

$$0\,B_1\,0\,B_2\,0\,\ldots\,B_{k-1}\,0, \;\; B_i \in \{1, 11\}$$

💡 '$00$ 없음·$111$ 없음' 조건 → $0$ 과 크기 $1$ 또는 $2$ 의 $1$-블록 교차.

#7 작은 문제로 쪼개기 6.EE.B.7 단계 2

$k - 1$ 분리 블록 중 '$11$' 블록 개수 $s$ ('$1$' 블록은 $k - 1 - s$).
길이: $0$ 이 $k$ 개 + $11$ 블록에서 $2s$ 개 + $1$ 블록에서 $k - 1 - s$ 개 = $2k + s - 1$.
$= 19$ 로 설정: $2k + s = 20$.

$$2k + s = 20, \;\; 0 \le s \le k - 1$$

💡 음이 아닌 두 정수의 일차식 — 디오판토스 부분 문제.

#2 빠짐없이 나열하기 6.EE.B.8 단계 3

$(k, s)$ 나열.
$s = 20 - 2k$.
$s \ge 0$: $k \le 10$.
$s \le k - 1$: $20 - 2k \le k - 1$, $3k \ge 21$, $k \ge 7$.
$k \in \{7, 8, 9, 10\}$.

$$k \in \{7, 8, 9, 10\}$$

💡 두 부등식으로 $k$ 는 $7$ 부터 $10$ 사이.

#2 빠짐없이 나열하기 7.SP.C.8 단계 4

각 $(k, s)$ 에서 수열 수 = $k - 1$ 개 분리 자리 중 $s$ 자리에 '$11$' 배치 = $\binom{k-1}{s}$.
$k = 7 \Rightarrow s = 6$, $\binom{6}{6} = 1$.
$k = 8 \Rightarrow s = 4$, $\binom{7}{4} = 35$.
$k = 9 \Rightarrow s = 2$, $\binom{8}{2} = 28$.
$k = 10 \Rightarrow s = 0$, $\binom{9}{0} = 1$.

$$\binom{6}{6} + \binom{7}{4} + \binom{8}{2} + \binom{9}{0} = 1 + 35 + 28 + 1$$

💡 $k - 1$ 분리 자리에서 '$11$' 자리 선택.

#9 더 쉬운 문제로 줄이기 4.NBT.B.4 단계 5

합: $1 + 35 + 28 + 1 = 65$.
정답 (C).

$$1 + 35 + 28 + 1 = 65$$

💡 네 경우의 합.

#9 더 쉬운 문제로 줄이기 4.NBT.B.4 단계 6

정답 (C) $65$.

$$\boxed{65}$$

💡 합을 선택지와 대조.

[1] #15 4.OA.C.5 수열 재구성. $0$ 으로 시작·끝, $00$ 없음 → $0$ 들이 한 개 또는 두 개의 $1$ 로 분리. $0 \, B_1 \, 0 \, B_

[2] #7 6.EE.B.7 $k - 1$ 분리 블록 중 '$11$' 블록 개수 $s$ ('$1$' 블록은 $k - 1 - s$). 길이: $0$ 이 $k$ 개 + $11$

[3] #2 6.EE.B.8 $(k, s)$ 나열. $s = 20 - 2k$. $s \ge 0$: $k \le 10$. $s \le k - 1$: $20 - 2k \le k

[4] #2 7.SP.C.8 각 $(k, s)$ 에서 수열 수 = $k - 1$ 개 분리 자리 중 $s$ 자리에 '$11$' 배치 = $\binom{k-1}{s}$. $k

[5] #9 4.NBT.B.4 합: $1 + 35 + 28 + 1 = 65$. 정답 (C).

[6] #9 4.NBT.B.4 정답 (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$ ✓.

대안 접근: 도구 #5 (패턴) — 점화식. 길이 $n$, $0$ 으로 끝나는 유효 수열 수 $f_n$ 은 $\ldots 10$ 또는 $\ldots 110$ 으로 끝 → $f_n = f_{n-2} + f_{n-3}$. 기초값 $f_2 = 1$, $f_4 = 1$, $f_5 = 1$ 등을 신중히 두고 반복 → $f_{19} = 65$. 초기 조건 함정이 있으므로 위의 이항계수 합이 더 안전.

사용된 CCSS 표준 (최저 학년 7)

4.NBT.B.4 여러 자릿수 정수 능숙히 덧셈·뺄셈 (최종 합 $1 + 35 + 28 + 1 = 65$.)
4.OA.C.5 주어진 규칙으로 수·도형 패턴 만들기 (수열을 $0$ 과 크기 $1$ 또는 $2$ 의 $1$-블록 교차로 재구성.)
6.EE.B.7 $px = q$ 꼴 방정식 세우기·풀기 ($0$ 개수와 '$11$' 블록 수로 $2k + s - 1 = 19$ 길이 방정식.)
6.EE.B.8 $x > c$ 또는 $x < c$ 꼴 부등식 세우기·수직선 표시 ($0 \le s \le k - 1$ 부등식으로 $k \in \{7, 8, 9, 10\}$ 한정.)
7.SP.C.8 조직된 목록·표·시뮬레이션으로 복합 사건 확률 구하기 ($k - 1$ 분리 자리에서 '$11$' 블록 배치를 $\binom{k-1}{s}$ 로 셈.)

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

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

사용된 CCSS 표준 (최저 학년 7)

비슷한 유형 더 풀어보기