AMC 10 · 2019 · #25

학년 8 arithmetic

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

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

📏 긴 풀이 💡 4 개 인사이트

문제

1 부터 50 까지의 정수 n 중

\frac{(n²-1)!}{(n!)ⁿ}

이 정수가 되는 n 의 개수는?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9(더 쉬운 문제): 관련 비율 M(n) = $\frac{(n²)!}{(n!)ⁿ}$ 은 항상 정수 (다항계수). 목표 식은 $\frac{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

M(n) = $\frac{(n²)!}{(n!)ⁿ}$ 은 항상 정수, 목표 식은 $\frac{M(n)}{n²}$ — n² ∣ M(n) 일 때만 정수.

\frac{(n²-1)!}{(n!)ⁿ}

\frac{M(n)}{n²}

, M(n) =

\frac{(n²)!}{(n!)ⁿ}

∈ Z_ ＞ 0

2STEP 2

여사건으로 세기: n² ∤ M(n) 인 n 을 세어 50 에서 빼고, 르장드르 공식으로 소인수 차수 계산.

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

3STEP 3

소수 n = p: v_p(M(p)) = (p+1) − p = 1 ＜ 2, 따라서 p² ∤ M(p) — 모든 소수 실패.

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

4STEP 4

1–50 의 소수는 2, 3, 5, …, 47 로 15 개, 각각 실패.

[1, 50] 의 소수 = 15 개

5STEP 5

합성수 점검: n = 1 성공, 그러나 n = 4 는 v₂(15!) = 11 ＜ 12 = v₂((4!)⁴) 로 실패 — 2 인수 하나 부족.

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

6STEP 6

다른 모든 합성수 n 은 성공: (n²−1)! 의 각 소인수가 (n!)ⁿ·n² 보다 넉넉 — 예: n = 6 에서 2 의 여유는 8 ≥ 2.

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

7STEP 7

총 실패는 소수 15 + 1 (n = 4) = 16, 성공은 50 − 16 = 34 — 정답 (D).

50 - 16 = 34

정답

검증. n = 1:

\frac{0!}{1!¹}

= 1 ✓ (성공). n = 2 (소수):

\frac{3!}{2!²}

\frac{6}{4}

= 1.5, 실패 ✓. n = 3 (소수):

\frac{8!}{6³}

\frac{40320}{216}

= 186.6, 실패 ✓. n = 4:

\frac{15!}{24⁴}

— v₂ 비교 분자 11 vs 분모 12, 비의 v₂ = -1 이라 정수 아님 ✓. n = 9 = 3²: M(9) =

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

비슷한 유형 더 풀어보기