AMC 10 · 2022 · #24

학년 6 counting

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

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

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

문제

길이 5인 문자열을 셉니다. 각 자리는 0부터 4까지의 숫자이고, 1부터 4까지의 각 값에 대해 그 값보다 엄격히 작은 숫자가 적어도 그 값만큼 있어야 합니다. 그런 문자열이 몇 개인지 구하세요.

답을 골라 클릭하세요.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

정렬해서 조건 다시 쓰기

정렬하면 조건이 단순해집니다.

d_(j) ＜ j, j = 1, 2, 3, 4

2STEP 2

길이 1 세기

가장 짧은 경우를 셉니다.

n = 1: 개수 = 1 = (1+1)¹⁻¹

3STEP 3

길이 2 세기

다음 길이도 셉니다.

n = 2: 개수 = 3 = (2+1)²⁻¹

4STEP 4

길이 3 세기

세 번째 길이도 셉니다.

n = 3: 개수 = 16 = (3+1)³⁻¹

5STEP 5

규칙 읽어내기

수열이 깔끔한 공식을 따릅니다.

개수(n) = (n+1)ⁿ⁻¹

6STEP 6

길이 5에 적용하기

길이 5에 넣으면 1296입니다.

6⁴ = 1296 → (E)

정답

1296

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

💡핵심 정리

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