AMC 10 · 2019 · #24

학년 8 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

factorialprime-numberslegendre-formulacombinatorial-identityprimality-test caseworkcomplementary-countingpattern-recognition ↑ 선수 지식: factorialprime-numberslegendre-formula

📏 긴 풀이 💡 4 개 인사이트

문제

1부터 50까지의 정수 n 중에서 n제곱 빼기 1의 계승을 n의 계승의 n제곱으로 나눈 값이 정수가 되는 것이 몇 개인지 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9(더 쉬운 문제): 관련 비율 M(n) = (n²)!/(n!)ⁿ은 항상 정수 (다항계수). 목표 식은 M(n)/n². 그러므로 질문은 n² ∣ M(n) 인 n 의 개수. 도구 #16(관점 바꾸기): 성공 대신 실패를 세서 50 에서 뺌. 도구 #7(작은 문제로 쪼개기): n 의 각 소인수 p 에 대해 르장드르로 v_p 비교. 도구 #5(패턴): 작은 n (n=1, 2, 3, 4, 5, 6, …) 시험해 실패 패턴 파악. 도구 #2(빠짐없이 나열): [1, 50]의 소수 + 특수 합성수 n = 4 나열.

1STEP 1

익숙한 값으로 바꾸기

이 값은 다항계수를 n의 제곱으로 나눈 것입니다.

((n²-1)!)/(n!)ⁿ = M(n)/n², M(n) = (n²)!/(n!)ⁿ ∈ Z_ ＞ 0

2STEP 2

여사건으로 세기

실패하는 n을 빼는 것이 빠릅니다.

답 = 50 - #{n : n² ∤ M(n)}

3STEP 3

소수는 언제나 실패

소수에서는 지수가 하나 모자랍니다.

v_p(M(p)) = (p+1) - p = 1 ＜ 2

4STEP 4

소수의 개수 세기

범위 안의 소수는 열다섯 개입니다.

[1, 50]의 소수 = 15 개

5STEP 5

소수가 아닌 예외 찾기

4에서도 지수가 모자랍니다.

n = 4: v₂(15!) = 11 ＜ 12 = v₂((4!)⁴)

6STEP 6

나머지 합성수 확인

다른 합성수는 여유가 충분합니다.

n = 6: v₂((6²-1)!) - v₂((6!)⁶) = 32 - 24 = 8 ≥ v₂(36) = 2

7STEP 7

빼서 마무리

빼면 34입니다.

50 - 16 = 34

정답

검증. n = 1: 0!/1!¹ = 1 ✓ (성공). n = 2 (소수): 3!/2!² = 6/4 = 1.5, 실패 ✓. n = 3 (소수): 8!/6³ = 40320/216 = 186.6, 실패 ✓. n = 4: 15!/24⁴ — v₂ 비교 분자 11 vs 분모 12, 비의 v₂ = -1이라 정수 아님 ✓. n = 9 = 3²: M(9) = (81)!/(9!)⁹, v₃(81!) = 27 + 9 + 3 + 1 = 40, v₃((9!)⁹) = 9 · v₃(9!) = 9 · 4 = 36. v₃(M(9)) = 40 - 36 = 4 ≥ v₃(81) = 4 ✓. n = 9 성공. 논리 일관: n ≠ 4 합성수는 모두 성공.

💡핵심 정리

이 AMC 12 문제는 8학년 지수 추적(르장드르 공식)과 소수·합성수 구분만 있으면 풀려요 — [1, 50]의 모든 소수 n (15 개)가 실패하고 n = 4도 (2의 인수가 하나 부족) 실패해서 50 - 16 = 34가 정수.