AMC 10 · 2019 · #9

학년 6 number-theory

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

factorialprime-numbersdivisibility-rulestriangular-numbersprimality-test identify-subproblemspattern-recognition ↑ 선수 지식: factorialprime-numbersdivisibility-rules

📏 중간 풀이 💡 3 개 인사이트

문제

What is the greatest three-digit positive integer $n$ for which the sum of the first $n$ positive integers is $\underline{not}$ a divisor of the product of the first $n$ positive integers?

답을 골라 클릭하세요.

(A)

995

(B)

996

(C)

997

(D)

998

(E)

999

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 처음 $n$ 개 양의 정수의 합 $1 + 2 + \cdots + n$ 이 곱 $1 \cdot 2 \cdots n = n!$ 의 약수가 되지 않는, 가장 큰 세 자리 양의 정수 $n$ 을 구하시오.

주어진 것: 처음 $n$ 개 양의 정수의 합 $= \dfrac{n(n+1)}{2}$; 처음 $n$ 개 양의 정수의 곱 $= n!$; 합이 곱의 약수가 되지 않는 가장 큰 세 자리 $n$ 을 찾음; 선택지: (A) $995$, (B) $996$, (C) $997$, (D) $998$, (E) $999$

구하는 것: 비약수 조건을 만족하는 가장 큰 세 자리 $n$

이해

문제 재정리: 처음 $n$ 개 양의 정수의 합 $1 + 2 + \cdots + n$ 이 곱 $1 \cdot 2 \cdots n = n!$ 의 약수가 되지 않는, 가장 큰 세 자리 양의 정수 $n$ 을 구하시오.

계획

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

보조 도구: #5 패턴 찾기, #3 가능성 지우기

$999$ 같은 큰 수는 직접 다루기 어려우므로 도구 #9: 작은 $n$ ($n = 2, 3, 4, 5, 6, 7, \ldots$) 부터 시도해 합이 곱의 약수인지 아닌지 관찰. 도구 #5 로 패턴 (특정 $n$ 만 실패) 발견. 도구 #3 으로 선택지를 큰 쪽부터 순서대로 검사.

실행 — 정답: B

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

작은 사례 직접 계산.
각 $n$ 에 대해 $S = \dfrac{n(n+1)}{2}$, $P = n!$ 을 구하고 $S \mid P$ 인지 확인.

$n = 2: S = 3, P = 2 \Rightarrow 3 \nmid 2$. $n = 3: S = 6, P = 6 \Rightarrow 6 \mid 6$. $n = 4: S = 10, P = 24 \Rightarrow 10 \nmid 24$. $n = 5: S = 15, P = 120 \Rightarrow 15 \mid 120$. $n = 6: S = 21, P = 720 \Rightarrow 21 \nmid 720$. $n = 7: S = 28, P = 5040 \Rightarrow 28 \mid 5040$.

💡 처음 몇 개 $n$ 직접 계산해 실패하는 경우 관찰.

#5 패턴 찾기 4.OA.B.4 단계 2

패턴 인식.
실패는 $n = 2, 4, 6$.
이들의 공통점은 $n + 1$ 이 소수 ($3, 5, 7$).
성공은 $n = 3 \Rightarrow n + 1 = 4$, $n = 5 \Rightarrow n + 1 = 6$, $n = 7 \Rightarrow n + 1 = 8$ — 모두 합성수.
가설: $n + 1$ 이 소수일 때만 실패.

$$\text{실패} \Leftrightarrow n + 1 \text{ 이 소수}$$

💡 실패는 $n + 1$ 이 소수일 때와 정확히 일치.

#5 패턴 찾기 6.NS.B.4 단계 3

왜 그런지 확인.
몫 $\dfrac{P}{S} = \dfrac{n!}{n(n+1)/2} = \dfrac{2 \cdot (n - 1)!}{n + 1}$.
정수가 되려면 $n + 1$ 이 $2 \cdot (n - 1)!$ 의 약수여야 함.
$n + 1$ 이 합성수 ($> 4$) 면 그 소인수는 모두 $\dfrac{n + 1}{2} \le n - 1$ 이하라 $(n - 1)!$ 에 들어 있어 약수가 됨.
$n + 1$ 이 홀수 소수 $p$ 면 $1, 2, \ldots, p - 2$ 중 어느 것도 $p$ 의 배수가 아니라 $p \nmid (n - 1)!$ 이고 $p$ 가 홀수라 $p \nmid 2$ — 실패.

$$\dfrac{n!}{\frac{n(n+1)}{2}} = \dfrac{2(n-1)!}{n+1}$$

💡 $n$ 과 $\dfrac{1}{2}$ 를 약분하면 $\dfrac{2(n-1)!}{n+1}$ — $n + 1$ 이 홀수 소수일 때만 실패.

#3 가능성 지우기 4.OA.B.4 단계 4

실패하는 $n$ 은 $n + 1$ 이 소수인 경우.
선택지에서 $n$ 이 가장 큰 것부터 차례로 $n + 1$ 의 소수 여부 확인.

$$n = 999: n + 1 = 1000 = 2^3 \cdot 5^3 \text{ (합성수)}$$

💡 $1000$ 은 명백히 소수가 아님.

#3 가능성 지우기 4.OA.B.4 단계 5

$n = 998$: $n + 1 = 999 = 3 \cdot 333 = 3^3 \cdot 37$.
합성수.

$$999 = 3 \cdot 333$$

💡 각 자리 합 $9 + 9 + 9 = 27$ 이 $3$ 의 배수이므로 $999$ 는 $3$ 으로 나눠짐.

#3 가능성 지우기 4.OA.B.4 단계 6

$n = 997$: $n + 1 = 998 = 2 \cdot 499$.
합성수.

$$998 = 2 \cdot 499$$

💡 $998$ 은 짝수라 $2$ 로 나눠짐.

#3 가능성 지우기 4.OA.B.4 단계 7

$n = 996$: $n + 1 = 997$.
$997$ 의 소수 여부 확인: $\sqrt{997} \approx 31.6$ 이하 소수 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ 중 어느 것도 $997$ 의 약수가 아님 ($997 / 7 = 142.4\ldots$, $997 / 11 = 90.6\ldots$, $997 / 13 = 76.7\ldots$, $997 / 17 = 58.6\ldots$, $997 / 19 = 52.5\ldots$, $997 / 23 = 43.3\ldots$, $997 / 29 = 34.4\ldots$, $997 / 31 = 32.2\ldots$).
따라서 $997$ 은 소수.

$$997 \text{ 은 소수}$$

💡 $\sqrt{997}$ 이하의 작은 소수로 시험해 약수가 없으면 $997$ 도 소수.

#3 가능성 지우기 4.NBT.A.2 단계 8

$n + 1$ 이 소수인 가장 큰 세 자리 $n$ 은 $996$.
즉 $n = 996$ 에서 합이 곱의 약수가 아님.
답 (B).

$$n = 996 \Rightarrow \textbf{(B)}$$

💡 위에서부터 $n + 1$ 이 소수인 첫 번째 선택지.

[1] #9 4.OA.B.4 작은 사례 직접 계산. 각 $n$ 에 대해 $S = \dfrac{n(n+1)}{2}$, $P = n!$ 을 구하고 $S \mid P$ 인지 확인

[2] #5 4.OA.B.4 패턴 인식. 실패는 $n = 2, 4, 6$. 이들의 공통점은 $n + 1$ 이 소수 ($3, 5, 7$). 성공은 $n = 3 \Rightar

[3] #5 6.NS.B.4 왜 그런지 확인. 몫 $\dfrac{P}{S} = \dfrac{n!}{n(n+1)/2} = \dfrac{2 \cdot (n - 1)!}{n +

[4] #3 4.OA.B.4 실패하는 $n$ 은 $n + 1$ 이 소수인 경우. 선택지에서 $n$ 이 가장 큰 것부터 차례로 $n + 1$ 의 소수 여부 확인.

[5] #3 4.OA.B.4 $n = 998$: $n + 1 = 999 = 3 \cdot 333 = 3^3 \cdot 37$. 합성수.

[6] #3 4.OA.B.4 $n = 997$: $n + 1 = 998 = 2 \cdot 499$. 합성수.

[7] #3 4.OA.B.4 $n = 996$: $n + 1 = 997$. $997$ 의 소수 여부 확인: $\sqrt{997} \approx 31.6$ 이하 소수 $2,

[8] #3 4.NBT.A.2 $n + 1$ 이 소수인 가장 큰 세 자리 $n$ 은 $996$. 즉 $n = 996$ 에서 합이 곱의 약수가 아님. 답 (B).

검토

합리성 확인: $n = 996$ 검산: $S = \dfrac{996 \cdot 997}{2} = 498 \cdot 997$, $P = 996!$. 몫 $= \dfrac{2 \cdot 995!}{997}$ 인데 $997$ 은 소수이고 $995!$ 안의 어느 인수보다도 크므로 분모 $997$ 이 약분되지 않음 — $S \nmid P$. ✓. 반대로 $n = 997$: $\dfrac{2 \cdot 996!}{998} = \dfrac{2 \cdot 996!}{2 \cdot 499} = \dfrac{996!}{499}$, 그리고 $499 < 996$ 이라 $499$ 가 $996!$ 의 인수로 들어 있어 정수 — $S \mid P$. 따라서 $997$ 은 조건 불만족, $996$ 이 정답.

대안 접근: 도구 #6 (추측·확인) 으로 선택지만 직접 시험. (E) 부터: $999 + 1 = 1000$ 합성수, $998 + 1 = 999$ 각 자리 합 $3$ 의 배수, $997 + 1 = 998$ 짝수, $996 + 1 = 997$ — $\sqrt{997}$ 이하 소수 검사로 약수 없음 → 소수, 멈춤. 같은 답.

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

4.OA.B.4 약수쌍·배수 찾기, 소수·합성수 판별 ($n + 1 \in \{1000, 999, 998, 997\}$ 의 소수·합성 여부 검사 및 소수성과 약수 조건 연결.)
6.NS.B.4 두 수의 최대공약수·최소공배수 찾기 ($\dfrac{n!}{n(n + 1)/2} = \dfrac{2(n-1)!}{n + 1}$ 로 약분해 공통 인수 정리.)
4.NBT.A.2 여러 자리 자연수를 읽고 쓰고 비교하기 ($n = 996$ 을 (B) 와 매칭.)

⭐ 이 AMC 10 문제는 사실 6학년 인수 분해만 알면 풀 수 있어요 — 합 $\dfrac{n(n+1)}{2}$ 가 $n!$ 의 약수가 안 되는 경우는 정확히 $n + 1$ 이 홀수 소수일 때. 선택지 중 $1000, 999, 998$ 은 모두 합성수이지만 $n = 996$ 일 때 $n + 1 = 997$ 이 소수. 답은 $996$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기