경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2019A · #25

학년 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 중

\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) = (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

다항계수로 바꿔 쓰기

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

((n²-1)!)/(n!)ⁿ = M(n)/n², M(n) = (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

50까지 소수 나열하기

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가 정수.

다항계수로 바꿔 쓰기
실패하는 경우 세기
소수인 경우 확인하기
50까지 소수 나열하기
작은 합성수 확인하기
나머지 모두 되는지 확인하기
실패 개수 빼기

가족의 부모 대시보드는 sensimlab.com에 있습니다.