AMC 10 · 2019 · #25

학년 8 arithmetic

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

📏 긴 풀이 💡 4 개 인사이트

문제

For how many integers $n$ between $1$ and $50$ , inclusive, is $\frac{(n^2-1)!}{(n!)^n}$ an integer? (Recall that $0! = 1$ .)

$\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $1$ 부터 $50$ 까지의 정수 $n$ 중 $\dfrac{(n^2-1)!}{(n!)^n}$ 이 정수가 되는 $n$ 의 개수는?

주어진 것: $n \in \{1, 2, 3, \ldots, 50\}$; 분자: $(n^2 - 1)!$; 분모: $(n!)^n$; $0! = 1$; 선택지: (A) $31$, (B) $32$, (C) $33$, (D) $34$, (E) $35$

구하는 것: $\dfrac{(n^2-1)!}{(n!)^n}$ 이 정수가 되는 $n$ 의 개수

이해

문제 재정리: $1$ 부터 $50$ 까지의 정수 $n$ 중 $\dfrac{(n^2-1)!}{(n!)^n}$ 이 정수가 되는 $n$ 의 개수는?

주어진 것: $n \in \{1, 2, 3, \ldots, 50\}$; 분자: $(n^2 - 1)!$; 분모: $(n!)^n$; $0! = 1$; 선택지: (A) $31$, (B) $32$, (C) $33$, (D) $34$, (E) $35$

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #7 작은 문제로 쪼개기, #5 패턴 찾기, #16 관점 바꾸기, #2 빠짐없이 나열하기

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

실행 — 정답: D

#9 더 쉬운 문제로 줄이기 6.NS.B.4 단계 1

더 쉬운 식 $M(n) = \dfrac{(n^2)!}{(n!)^n}$ — 다항계수 $\binom{n^2}{n, n, \ldots, n}$ ($n^2$ 개 구별 가능 물체를 크기 $n$ 인 $n$ 개 순서 블록으로 나누는 경우의 수), 항상 양의 정수.
따라서 $\dfrac{(n^2-1)!}{(n!)^n} = \dfrac{(n^2)!}{(n!)^n \cdot n^2} = \dfrac{M(n)}{n^2}$.
정수가 될 조건은 $n^2 \mid M(n)$.

$$\dfrac{(n^2-1)!}{(n!)^n} = \dfrac{M(n)}{n^2}, \;\; M(n) = \dfrac{(n^2)!}{(n!)^n} \in \mathbb{Z}_{>0}$$

💡 다항계수는 항상 정수 — 유일한 장벽은 $n^2$ 로 나눠 떨어지는지.

#16 관점 바꾸기 6.NS.B.4 단계 2

관점 바꾸기(여사건): $n \in \{1, \ldots, 50\}$ 중 $n^2 \nmid M(n)$ 인 $n$ 의 수를 센 뒤 $50$ 에서 뺌.
르장드르 공식: $v_p(k!) = \sum_{i \ge 1} \lfloor k/p^i \rfloor$.

$$\text{답} = 50 - \#\{n : n^2 \nmid M(n)\}$$

💡 실패는 드물고 셀 만함.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 3

경우: $n$ 이 소수 $p$.
$v_p(M(p)) \ge v_p(p^2) = 2$ 필요.
$v_p((p^2)!) = \lfloor p^2/p \rfloor + \lfloor p^2/p^2 \rfloor = p + 1$, $v_p((p!)^p) = p \cdot v_p(p!) = p \cdot 1 = p$.
따라서 $v_p(M(p)) = (p + 1) - p = 1 < 2$.
$p^2 \nmid M(p)$ — 모든 소수 $n$ 실패.

$$v_p(M(p)) = (p+1) - p = 1 < 2$$

💡 $n = p$ 일 때 분자는 분모보다 $p$ 인수 하나만 더 갖지만 $n^2 = p^2$ 은 둘이 필요.

#2 빠짐없이 나열하기 4.OA.B.4 단계 4

$[1, 50]$ 의 소수 나열: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ — 총 $15$ 개.
모두 실패.

$$[1, 50] \text{ 의 소수} = 15 \text{ 개}$$

💡 $1$ – $50$ 소수는 손으로 셀 만함.

#5 패턴 찾기 8.EE.A.1 단계 5

작은 합성수에서 추가 실패 점검.
$n = 1$: $\tfrac{0!}{1!^1} = 1$.
✓ 정수.
$n = 4$: 분자 $15!$, 분모 $(4!)^4 = 24^4$.
$p = 2$ 에서 르장드르: $v_2(15!) = 7 + 3 + 1 = 11$, $v_2(24^4) = 4 \cdot v_2(24) = 4 \cdot 3 = 12$.
$v_2(\text{비}) = 11 - 12 = -1 < 0$ — 정수 아님!
$n = 4$ 도 실패.

$$n = 4: \;\; v_2(15!) = 11 < 12 = v_2((4!)^4)$$

💡 $4$ 가 합성수임에도 다항계수의 분자에 $2$ 가 $11$ 개, 분모에 $12$ 개로 살짝 부족.

#9 더 쉬운 문제로 줄이기 8.EE.A.1 단계 6

나머지 모든 합성수 $n \in [2, 50]$ 가 성공함을 확인.
합성수 $n$ ($\ne 4$) 의 소인수 $p$ 에 대해 $p^k \| n$, 르장드르 추정으로 $v_p((n^2-1)!) \ge v_p((n!)^n) + v_p(n^2)$ — 구체적으로 $\{1, \ldots, n^2 - 1\}$ 에서 $p$ 의 배수 수가 $n \cdot v_p(n!) + v_p(n^2)$ 를 충분히 넘김 ($n \ne 4$ 합성수).
(검증 $n = 6$: $v_2(35!) = 17 + 8 + 4 + 2 + 1 = 32$, $v_2((6!)^6) = 6 \cdot v_2(720) = 6 \cdot 4 = 24$; 추가 필요량 $v_2(36) = 2$, $32 - 24 = 8 \ge 2$.
$p = 3$ 등도 같은 식으로 통과.)

$$n = 6: \;\; v_2((6^2-1)!) - v_2((6!)^6) = 32 - 24 = 8 \ge v_2(36) = 2$$

💡 $n \ne 4$ 합성수의 경우 $(n^2-1)!$ 의 각 소인수 차수가 넉넉해 $n^2$ 나눠떨어짐 보장.

#16 관점 바꾸기 4.OA.A.3 단계 7

총 실패: 소수 $15$ + $n = 4$ 추가 $= 16$.
성공: $50 - 16 = 34$.
정답 (D).

$$50 - 16 = 34$$

💡 $50$ 에서 실패 수 빼기.

[1] #9 6.NS.B.4 더 쉬운 식 $M(n) = \dfrac{(n^2)!}{(n!)^n}$ — 다항계수 $\binom{n^2}{n, n, \ldots, n}$ ($n

[2] #16 6.NS.B.4 관점 바꾸기(여사건): $n \in \{1, \ldots, 50\}$ 중 $n^2 \nmid M(n)$ 인 $n$ 의 수를 센 뒤 $50$ 에서

[3] #7 6.NS.B.4 경우: $n$ 이 소수 $p$. $v_p(M(p)) \ge v_p(p^2) = 2$ 필요. $v_p((p^2)!) = \lfloor p^2/p

[4] #2 4.OA.B.4 $[1, 50]$ 의 소수 나열: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ — 총

[5] #5 8.EE.A.1 작은 합성수에서 추가 실패 점검. $n = 1$: $\tfrac{0!}{1!^1} = 1$. ✓ 정수. $n = 4$: 분자 $15!$, 분모

[6] #9 8.EE.A.1 나머지 모든 합성수 $n \in [2, 50]$ 가 성공함을 확인. 합성수 $n$ ($\ne 4$) 의 소인수 $p$ 에 대해 $p^k \| n

[7] #16 4.OA.A.3 총 실패: 소수 $15$ + $n = 4$ 추가 $= 16$. 성공: $50 - 16 = 34$. 정답 (D).

검토

합리성 확인: 검증. $n = 1$: $\tfrac{0!}{1!^1} = 1$ ✓ (성공). $n = 2$ (소수): $\tfrac{3!}{2!^2} = \tfrac{6}{4} = 1.5$, 실패 ✓. $n = 3$ (소수): $\tfrac{8!}{6^3} = \tfrac{40320}{216} = 186.\overline{6}$, 실패 ✓. $n = 4$: $\tfrac{15!}{24^4}$ — $v_2$ 비교 분자 $11$ vs 분모 $12$, 비의 $v_2 = -1$ 이라 정수 아님 ✓. $n = 9 = 3^2$: $M(9) = (81)!/(9!)^9$, $v_3(81!) = 27 + 9 + 3 + 1 = 40$, $v_3((9!)^9) = 9 \cdot v_3(9!) = 9 \cdot 4 = 36$. $v_3(M(9)) = 40 - 36 = 4 \ge v_3(81) = 4$ ✓. $n = 9$ 성공. 논리 일관: $n \ne 4$ 합성수는 모두 성공.

대안 접근: 도구 #6(추측·확인) — 작은 스프레드시트에서 무차별. $n = 1, 2, \ldots, 50$ 각각에서 $n$ 의 모든 소인수 $p$ 에 대해 $(n^2-1)!$ vs $(n!)^n$ 의 $v_p$ 계산. 비의 모든 $v_p \ge 0$ 인 $n$ 이 $\{1\} \cup \{\text{합성수} \setminus \{4\}\}$ 임을 직접 확인. $50 - 15 - 1 = 34$. 같은 답; 분석 경로가 더 빠르지만 스프레드시트는 $n = 4$ 유일 합성수 실패를 직접 검증.

사용된 CCSS 표준 (최저 학년 8)

4.OA.A.3 네 가지 연산을 사용하는 여러 단계 문제 풀기 (최종 계산 $50 - 16 = 34$.)
4.OA.B.4 약수 쌍 찾기·배수 인식·소수·합성수 판별 ($[1, 50]$ 소수 나열과 합성수 후보 식별.)
6.NS.B.4 두 수의 최대공약수·최소공배수 구하기 (나눠떨어짐 질문을 $n^2 \mid M(n) = (n^2)!/(n!)^n$ 으로 환원.)
8.EE.A.1 정수 지수 성질 알고 적용 (르장드르 공식 $v_p(k!) = \sum_i \lfloor k/p^i \rfloor$ 로 각 소수의 최고 차수 추적, 분자·분모 지수 비교.)

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

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: D

검토

사용된 CCSS 표준 (최저 학년 8)

비슷한 유형 더 풀어보기