combinations-basicsystematic-enumerationpattern-recognitioneasier-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∈{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.)
문제 재정리: 길이 $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$
구하는 것: 조건을 만족하는 문자열의 개수
이해
문제 재정리: 길이 $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$".
합리성 확인: 수치 점검. 조건 없는 전체 문자열 수 $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$.
⭐ 이 AMC 10 문제는 이미 배운 6학년 거듭제곱만 있으면 풀려요 — 자리를 정렬하면 규칙이 $d_{(j)} < j$ 로 깔끔해지고, $n = 1, 2, 3$ 을 손으로 풀면 개수가 $1, 3, 16$. 패턴 $(n+1)^{n-1}$ 을 짚어 $n = 5$ 에서 $6^4 = 1296$.