AMC 10 · 2022 · #24

학년 6 arithmetic

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

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

문제

길이 5 인 문자열 d₁ d₂ d₃ d₄ d₅ 가 각 d_i ∈ {0, 1, 2, 3, 4} 이고, 각 j ∈ {1, 2, 3, 4} 에 대해 다섯 개 자리 중 적어도 j 개가 j 보다 작은 그런 문자열의 개수를 구합니다.

답을 골라 클릭하세요.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

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

풀이 과정

전략 더 쉬운 문제로 줄이기

원 문제 (길이 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) 로 깔끔해집니다. d_(5) 는 자유.

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

2STEP 2

길이 1, {0}: 문자열 0 만 조건을 만족 → 개수 1 = 2⁰.

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

3STEP 3

길이 2, {0, 1}: 0 이 적어도 하나 필요 → 00, 01, 10, 개수 3 = 3¹.

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

4STEP 4

길이 3, {0, 1, 2}: 다중집합 경우 분석으로 1 + 6 + 9 = 16 = 4².

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

5STEP 5

개수 1, 3, 16 이 정확히 (n+1)ⁿ⁻¹ (2⁰, 3¹, 4²) — 고전적 주차 함수 개수입니다.

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

6STEP 6

n = 5 대입: (5+1)⁵⁻¹ = 6⁴ = 1296, 선택지 (E).

6⁴ = 1296 → (E)

정답

1296

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

💡핵심 정리

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