AMC 10 · 2024 · #16

학년 8 counting

유형 Arithmetic Expression Decomposition └ 세부 유형 Successive Multiplicative Steps

combinations-basicfactorialprime-factorizationlegendre-formula identify-subproblemsconvert-to-algebrapattern-recognition ↑ 선수 지식: combinations-basicfactorialprime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

16명을 구별되지 않는 4명짜리 위원회 네 개로 나누고, 각 위원회 안에서 위원장 한 명과 서기 한 명을 뽑습니다. 이렇게 이름표까지 붙인 배치의 총 개수를 N이라 합시다. N을 3의 r제곱 곱하기 M으로 쓰되 M은 3으로 나누어지지 않는다고 할 때 r을 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

우리에게 필요한 건 N 의 값이 아니라 N 안에 든 3의 개수뿐입니다. 도구 #7(작은 문제로 쪼개기)이 N 을 깔끔한 곱으로 분해합니다 — (i) 분할 수 16!/(4!)⁵, (ii) 위원회 한 개당 역할 배정 12⁴. 도구 #13(대수로 바꾸기)으로 N = 16! · 12⁴ / (4!)⁵ 식을 얻습니다. 도구 #5(패턴 찾기)는 "n! 안의 소수 p 의 지수 = p, 2p, 3p, … 가 주는 p + p², 2p², … 가 주는 여분" 이라는 르장드르 패턴을 적용합니다. 도구 #8(단위 살펴보기)은 소수 3을 "세는 단위" 로 두고 곱과 나눗셈을 따라가는 회계 기법으로 어려운 셈을 한 장의 v₃ 계산표로 압축합니다.

1STEP 1

배치의 개수를 식으로

나누기와 뽑기를 곱해 팩토리얼 식을 만듭니다.

N = 16!/(4!)⁵ · 12⁴ = (16! · 12⁴)/(4!)⁵

2STEP 2

3의 지수만 추적하기

지수는 더하고 빼기만 하면 됩니다.

r = v₃(N) = v₃(16!) + v₃(12⁴) - v₃((4!)⁵)

3STEP 3

16 팩토리얼의 3 지수

르장드르 공식으로 6입니다.

v₃(16!) = ⌊ 16/3 ⌋ + ⌊ 16/9 ⌋ + ⌊ 16/27 ⌋ + … = 5 + 1 + 0 = 6

4STEP 4

12의 네제곱

12마다 3이 하나씩, 모두 4입니다.

12 = 2² · 3 → v₃(12⁴) = 4 · v₃(12) = 4

5STEP 5

분모의 3 지수

4 팩토리얼 다섯 개에서 5가 나옵니다.

4! = 24 = 2³ · 3 → v₃((4!)⁵) = 5 · v₃(4!) = 5

6STEP 6

더하고 빼기

6 더하기 4 빼기 5는 5입니다.

r = v₃(N) = 6 + 4 - 5 = 5 → (A)

정답

크기를 한 번 더 확인합니다. 분자 16! 만으로 3이 여섯 개(3, 6, 9, 12, 15 에서 다섯 개 + 9 = 3² 에서 하나 더), 역할 인자 12⁴가 네 개 더해 분자 합 열 개. 분모 (4!)⁵가 다섯 개를 회수해 남는 건 10 - 5 = 5. 분해된 모든 셈이 작은 정수(최대 6)라 답이 다섯 거듭제곱 정도임은 자연스럽고, 선택지 5, 6, 7, 8, 9도 그 근방에 몰려 있습니다. 흔한 실수는 "위원회 구별 안 됨" 의 4! 나눗셈을 잊는 것 — 그러면 v₃(4!) = 1 만큼 빠져 답이 6으로 한 칸 밀려나는데, 그게 바로 함정 (B).

💡핵심 정리

거대한 셈 문제가 "3이 몇 개 들어 있나?" 를 물으면 답을 계산하지 말고 조각마다 3만 세세요. 16! 에서 다섯, 12⁴ 에서 네 개 더, 그러나 (4!)⁵가 다섯 개를 빼앗아 남는 건 r = 5.