AMC 10 · 2022 · #24

학년 6 arithmetic

combinations-basicsystematic-enumerationpattern-recognition easier-related-problempattern-recognitionsystematic-enumeration ↑ 선수 지식: combinations-basic

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

문제

How many strings of length $5$ formed from the digits $0$ , $1$ , $2$ , $3$ , $4$ are there such that for each $j \in \{1,2,3,4\}$ , at least $j$ of the digits are less than $j$ ? (For example, $02214$ satisfies this condition
because it contains at least $1$ digit less than $1$ , at least $2$ digits less than $2$ , at least $3$ digits less
than $3$ , and at least $4$ digits less than $4$ . The string $23404$ does not satisfy the condition because it
does not contain at least $2$ digits less than $2$ .)

$\textbf{(A) }500\qquad\textbf{(B) }625\qquad\textbf{(C) }1089\qquad\textbf{(D) }1199\qquad\textbf{(E) }1296$

답을 골라 클릭하세요.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 길이 $5$ 인 문자열 $d_1 d_2 d_3 d_4 d_5$ 가 각 $d_i \in \{0, 1, 2, 3, 4\}$ 이고, 각 $j \in \{1, 2, 3, 4\}$ 에 대해 다섯 개 자리 중 적어도 $j$ 개가 $j$ 보다 작은 그런 문자열의 개수를 구합니다.

주어진 것: 자릿값은 $\{0, 1, 2, 3, 4\}$ 에서 선택, 길이 $5$; 각 $j \in \{1, 2, 3, 4\}$ 에 대해 $< j$ 인 자리 수 $\ge j$; 예시 $02214$ 는 조건 만족, $23404$ 는 ($< 2$ 인 자리가 $1$ 개뿐이라) 불만족; 선택지: (A) $500$, (B) $625$, (C) $1089$, (D) $1199$, (E) $1296$

구하는 것: 조건을 만족하는 문자열의 개수

이해

계획

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

보조 도구: #5 패턴 찾기, #2 빠짐없이 나열하기, #3 가능성 지우기

원 문제 (길이 $5$, 알파벳 $\{0, \ldots, 4\}$) 의 $3125$ 개 문자열을 손으로 거르긴 너무 많습니다. 도구 #9(더 쉬운 문제) — 같은 종류의 문제를 길이 $n$, 알파벳 $\{0, \ldots, n-1\}$ 로 $n = 1, 2, 3$ 에 대해 시도. 도구 #2(빠짐없이 나열) 로 작은 경우를 손으로. 도구 #5(패턴 찾기): 개수 $1, 3, 16$ 이 정확히 $(n+1)^{n-1}$ — 유명한 \emph{주차함수(parking function)} 의 개수입니다. $n = 5$ 에 대해 $6^4 = 1296$, 선택지 (E). 도구 #3(가능성 지우기) 으로 선택지 (C) $1089 = 33^2$ 와 (D) $1199$ — 깔끔한 지수 패턴에서 나올 수 없음 — 를 제외.

실행 — 정답: E

#9 더 쉬운 문제로 줄이기 6.EE.B.8 단계 1

조건을 깔끔하게 다시 씁니다.
다섯 자리를 $d_{(1)} \le \ldots \le d_{(5)}$ 로 정렬할 때, "$j$ 보다 작은 자리가 적어도 $j$ 개" 는 "$j$ 번째로 작은 자리값 $d_{(j)} < j$" 와 동치.
따라서 조건은 정확히 $d_{(1)} = 0$, $d_{(2)} \le 1$, $d_{(3)} \le 2$, $d_{(4)} \le 3$ ($d_{(5)}$ 는 $\{0, 1, 2, 3, 4\}$ 의 무엇이든).

$$d_{(j)} < j, \;\; j = 1, 2, 3, 4$$

💡 6학년 — 정렬된 수열에 대한 부등식 조건이 원래의 "개수" 조건과 동치.

#9 더 쉬운 문제로 줄이기 K.OA.A.5 단계 2

아주 작은 경우 $n = 1$.
길이 $1$, $\{0\}$ 에서 "$1$ 보다 작은 자리가 적어도 $1$ 개".
유일한 문자열: $0$.
개수 $= 1 = 2^0$.

$$n = 1: \text{개수} = 1 = (1+1)^{1-1}$$

💡 유치원 — $1$ 까지 세기.

#2 빠짐없이 나열하기 2.OA.C.4 단계 3

작은 경우 $n = 2$.
길이 $2$, $\{0, 1\}$ 에서 "$1$ 보다 작은 자리 $\ge 1$" (그리고 $2$ 보다 작은 자리 $\ge 2$ 는 모든 자리가 $\{0, 1\}$ 이라 자동 만족).
적어도 하나의 $0$ 이 필요.
문자열: $00, 01, 10$, 개수 $= 3 = 3^1$.

$$n = 2: \text{개수} = 3 = (2+1)^{2-1}$$

💡 2학년 — 길이 $2$ 짜리 이진 문자열 $4$ 개에서 $11$ 만 제외.

#2 빠짐없이 나열하기 4.OA.B.4 단계 4

작은 경우 $n = 3$.
길이 $3$, $\{0, 1, 2\}$ 에서 "적어도 하나의 $0$" 그리고 "$\{0, 1\}$ 에 속하는 자리가 $\ge 2$".
다중집합별 경우 분석: $\{0, 0, 0\}$: $1$ 개.
$\{0, 0, x\}$ ($x \in \{1, 2\}$): $2 \cdot \binom{3}{1} = 6$.
$\{0, 1, x\}$ ($x \in \{1, 2\}$): $\{0, 1, 1\}$ 의 배열 $3$ 개, $\{0, 1, 2\}$ 의 배열 $6$ 개, 합 $9$.
총합 $= 1 + 6 + 9 = 16 = 4^2$.

$$n = 3: \text{개수} = 16 = (3+1)^{3-1}$$

💡 4학년 — 유효 다중집합을 경우별로 나누고 각 배열 수 계산.

#5 패턴 찾기 4.OA.C.5 단계 5

패턴을 찾습니다.
$1, 3, 16, \ldots$ 이 $(n+1)^{n-1}$ 에 정확히 들어맞습니다: $2^0 = 1, 3^1 = 3, 4^2 = 16$.
(사실 이것이 고전적 \emph{주차 함수} 개수입니다 — 길이 $n$, 알파벳 $\{0, \ldots, n-1\}$ 에서 정렬 조건 $d_{(j)} < j$ 는 주차 함수의 정의 그 자체이고, 닫힌 식 $(n+1)^{n-1}$ 은 Cayley 의 유명한 결과입니다.)

$$\text{개수}(n) = (n+1)^{n-1}$$

💡 4학년 — 세 데이터 점이 이미 $(n+1)^{n-1}$ 패턴을 짚어줍니다.

#5 패턴 찾기 6.EE.A.1 단계 6

$n = 5$ 에 적용.
개수 $= (5+1)^{5-1} = 6^4 = 36 \cdot 36 = 1296$, 선택지 (E).

$$6^4 = 1296 \;\Rightarrow\; \textbf{(E)}$$

💡 6학년 — 패턴에 $n = 5$ 를 대입.

[1] #9 6.EE.B.8 조건을 깔끔하게 다시 씁니다. 다섯 자리를 $d_{(1)} \le \ldots \le d_{(5)}$ 로 정렬할 때, "$j$ 보다 작은 자리가

[2] #9 K.OA.A.5 아주 작은 경우 $n = 1$. 길이 $1$, $\{0\}$ 에서 "$1$ 보다 작은 자리가 적어도 $1$ 개". 유일한 문자열: $0$. 개수

[3] #2 2.OA.C.4 작은 경우 $n = 2$. 길이 $2$, $\{0, 1\}$ 에서 "$1$ 보다 작은 자리 $\ge 1$" (그리고 $2$ 보다 작은 자리 $\

[4] #2 4.OA.B.4 작은 경우 $n = 3$. 길이 $3$, $\{0, 1, 2\}$ 에서 "적어도 하나의 $0$" 그리고 "$\{0, 1\}$ 에 속하는 자리가

[5] #5 4.OA.C.5 패턴을 찾습니다. $1, 3, 16, \ldots$ 이 $(n+1)^{n-1}$ 에 정확히 들어맞습니다: $2^0 = 1, 3^1 = 3, 4^

[6] #5 6.EE.A.1 $n = 5$ 에 적용. 개수 $= (5+1)^{5-1} = 6^4 = 36 \cdot 36 = 1296$, 선택지 (E).

검토

합리성 확인: 수치 점검. 조건 없는 전체 문자열 수 $5^5 = 3125$. 답 $1296$ 은 그 약 $41\%$ — 조건이 적당히 제한적이라 그럴듯합니다(작은 숫자가 많은 문자열은 거의 다 만족, $3, 4$ 위주 문자열만 위반). 또 $1296 = 6^4$ 은 주차함수 형태의 깔끔한 지수형. 작은 경우 $1, 3, 16$ 이 손으로 검증되고 정확히 $(n+1)^{n-1}$ 패턴이므로 $n = 5$ 에서도 신뢰 가능.

대안 접근: 도구 #2(직접 경우 분석) 을 $n = 5$ 에 적용: 다중집합의 서로 다른 자리값 수 ($1, 2, 3, 4, 5$) 별로 나눠 정렬-조건을 만족하는 다중집합을 찾고 각 다중집합의 배열 수를 계산. 참고 풀이가 이 방식이며 $1 + 75 + 500 + 600 + 120 = 1296$. 도구 #3(가능성 지우기): $6^4 = 1296$ 인 선택지는 (E) 뿐. (B) $625 = 5^4$ 는 학생이 $5^{n-1}$ 로 잘못 쓴 경우의 함정이고, (A) $500$ 은 경우 분석 중 한 부분합 — 둘 다 작은 경우 패턴으로 탈락.

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

K.OA.A.5 $5$ 이내에서 능숙하게 더하고 빼기 (길이 $1$ 의 유일한 문자열 $0$ 을 세기.)
2.OA.C.4 직사각형 배열의 대상 총수를 덧셈으로 구하기 (길이 $2$ 이진 문자열 $4$ 개를 나열하고 $1$ 개 위반 제외.)
4.OA.B.4 어떤 정수의 모든 약수 쌍 찾기; 한 자릿수의 배수 여부 판별 (길이 $3$ 다중집합을 경우별로 나누고 배열 수 계산.)
4.OA.C.5 주어진 규칙을 따르는 수·도형 패턴 생성 (데이터 점 $1, 3, 16$ 에서 패턴 $(n+1)^{n-1}$ 읽어내기.)
6.EE.A.1 정수 지수를 포함한 수식의 작성과 계산 ($n = 5$ 에서 $6^4 = 1296$ 계산.)
6.EE.B.8 제약 조건을 $x > c$ 또는 $x < c$ 부등식으로 쓰기 (원 조건을 정렬된 자리에 대한 부등식 $d_{(j)} < j$ 로 재서술.)

⭐ 이 AMC 10 문제는 이미 배운 6학년 거듭제곱만 있으면 풀려요 — 자리를 정렬하면 규칙이 $d_{(j)} < j$ 로 깔끔해지고, $n = 1, 2, 3$ 을 손으로 풀면 개수가 $1, 3, 16$. 패턴 $(n+1)^{n-1}$ 을 짚어 $n = 5$ 에서 $6^4 = 1296$.