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 개 인사이트

문제

처음 n 개 양의 정수의 합 1 + 2 + … + n 이 곱 1 · 2 … n = n! 의 약수가 되지 않는, 가장 큰 세 자리 양의 정수 n 을 구하시오.

답을 골라 클릭하세요.

(A)

995

(B)

996

(C)

997

(D)

998

(E)

999

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

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

n = 2: S = 3, P = 2 → 3 ∤ 2. n = 3: S = 6, P = 6 → 6 ∣ 6. n = 4: S = 10, P = 24 → 10 ∤ 24. n = 5: S = 15, P = 120 → 15 ∣ 120. n = 6: S = 21, P = 720 → 21 ∤ 720. n = 7: S = 28, P = 5040 → 28 ∣ 5040.

2STEP 2

실패는 n = 2, 4, 6 — 모두 n + 1 이 소수 (3, 5, 7); 성공은 합성수. 가설: n + 1 이 소수면 실패.

실패 ⇔ n + 1 이 소수

3STEP 3

정리: $\frac{P}{S}$ = $\frac{2(n - 1)!}{n + 1}$ . n + 1 이 합성수면 약분되고, 홀수 소수면 (n - 1)! 도 2 도 못 나눠 실패.

\frac{n!}{\frac{n(n+1)}{2}}

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

4STEP 4

실패하는 n 은 n + 1 이 소수인 경우이니 위에서부터 검사. n = 999 → n + 1 = 1000 = 2³ · 5³ 합성수. 아래로.

n = 999: n + 1 = 1000 = 2³ · 5³ (합성수)

5STEP 5

n = 998 → n + 1 = 999 = 3 · 333 = 3³ · 37 합성수. 계속.

999 = 3 · 333

6STEP 6

n = 997 → n + 1 = 998 = 2 · 499 합성수. 아직 아님.

998 = 2 · 499

7STEP 7

n = 996 → n + 1 = 997; √997 ≈ 31 이하 소수로 시험해 나눠지지 않으니 997 은 소수 — 합이 곱의 약수가 아님.

997 은 소수

8STEP 8

따라서 n + 1 이 소수인 가장 큰 세 자리 n 은 996 — 합이 곱의 약수가 아님. 답 (B).

n = 996 → (B)

정답

996

n = 996 검산: S =

\frac{996 · 997}{2}

= 498 · 997, P = 996!. 몫 =

\frac{2 · 995!}{997}

인데 997 은 소수이고 995! 안의 어느 인수보다도 크므로 분모 997 이 약분되지 않음 — S ∤ P. ✓. 반대로 n = 997:

\frac{2 · 996!}{998}

\frac{2 · 996!}{2 · 499}

\frac{996!}{499}

, 그리고 499 ＜ 996 이라 499 가 996! 의 인수로 들어 있어 정수 — S ∣ P. 따라서 997 은 조건 불만족, 996 이 정답.

💡핵심 정리

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

비슷한 유형 더 풀어보기