AMC 10 · 2009 · #19

학년 9 number-theory

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

difference-of-squarespolynomial-factoringprime-numberscompleting-the-square pattern-recognitionbound-inequality-then-enumerate ↑ 선수 지식: polynomial-factoringprime-numbers

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 사차식 규칙을 모든 양의 정수에 적용한다. 그 결과가 소수인 경우의 값을 모두 더하여라.

답을 골라 클릭하세요.

(A)

794

(B)

796

(C)

798

(D)

800

(E)

802

풀이 과정

전략 다르게 정리하기

도구 #15(다르게 정리하기)가 뼈대이다. n⁴ - 360n² + 400은 쓰여 있는 그대로는 소수 여부에 대해 아무것도 말해 주지 않는다. 소수 여부는 인수분해에 대한 이야기인데 이 꼴에는 인수가 보이지 않기 때문이다. 같은 식을 두 제곱의 차로 다시 묶으면 곱의 꼴이 되고, 곱이야말로 소수 문제에 답할 수 있는 형태다. 도구 #6(추측하고 확인하기)은 작업의 문을 열고 — 몇 개를 대입해 결과의 모양을 본다 — 마지막에 남은 두 후보를 검사하며 닫는다. 도구 #14(극단의 원리)는 큰 쪽 인수가 가질 수 있는 최솟값을 못 박는데, 이것이 논증 전체의 경첩이다. 도구 #3(가능성 지우기)는 그 하한을 이용해, 구간별로 나누지 않고 한 번에 거의 모든 n 을 지운다. 도구 #11(거꾸로 풀기)는 인수가 만족해야 하는 조건에서 출발해 그런 n 을 역으로 구한다.

1STEP 1

몇 개 대입해 보기

값을 몇 개 보면 결과가 대개 합성수다.

f(1) = 41, f(2) = -1024, f(19) = 761, f(20) = 16400

2STEP 2

숨어 있는 제곱의 차 찾기

그 식이 제곱의 차를 숨기고 있다.

(n²+20)² = n⁴ + 40n² + 400 → f(n) = (n²+20)² - 400n² = (n²+20)² - (20n)²

3STEP 3

인수분해하고 항등식 확인하기

그것이 식을 두 괄호로 인수분해한다.

f(n) = (n² - 20n + 20)(n² + 20n + 20) = A · B

4STEP 4

큰 인수의 하한 잡기

큰 괄호는 언제나 1보다 훨씬 크다.

B = (n+10)² - 80 ≥ 11² - 80 = 41 (모든 n ≥ 1)

5STEP 5

작은 인수를 1로 강제하기

그래서 소수 조건이 작은 괄호를 1로 강제한다.

f(n)이 소수, B ≥ 41 → A ≥ 1; A ≥ 2 → f(n) = A · B 는 합성수 → A = 1

6STEP 6

살아남는 입력 구하기

풀면 입력이 둘뿐이다.

n² - 20n + 20 = 1 → n² - 20n + 19 = 0 → (n-1)(n-19) = 0 → n = 1, 19

7STEP 7

두 후보를 검증하고 더하기

둘 다 확인해 더하면 802, 보기 (E).

f(1) = 41, f(19) = 761, 41 + 761 = 802 → (E)

정답

802

서로 독립적인 세 가지 확인. 첫째, 인수분해: n = 3 에서 A = 9 - 60 + 20 = -31, B = 9 + 60 + 20 = 89 이므로 A · B = -2759이고, 이는 f(3) = 81 - 3240 + 400 = -2759와 일치한다. 둘째, 논리가 빈틈없이 모든 입력을 덮는다: B ≥ 41은 모든 n ≥ 1 에서 성립하고, 'A ≤ 0, A = 1, A ≥ 2' 라는 분류는 정수 위에서 남김이 없으므로 빠져나가는 n 이 없다. 셋째, 충분성 검사를 실제로 수행했다 — 41과 761을 가정하지 않고 각각 소수 판정했는데, A = 1 만으로는 '이 입력들만 가능하다' 를 보일 뿐 '이 입력들이 실제로 통한다' 를 보이지는 못하므로 이 검사가 꼭 필요하다. 선택지에 대한 경고 하나: 802는 가장 큰 선택지라서, 41과 761을 찾고 합이 이미 최대 선택지에 닿았다는 이유로 멈춘다면 그것은 증명이 아니라 짐작이다. 선택지들이 서로 8 이내로 붙어 있는 것은 바로 그 지름길을 유혹하기 위해서이며, 인수분해가 짐작을 논증으로 바꿔 준다.

💡핵심 정리

인수분해가 안 될 것 같은 사차식도 제곱의 차를 숨기고 있을 수 있다. f(n) = (n²-20n+20)(n²+20n+20)로 쓰면 두 번째 인수는 항상 41 이상이므로, 소수가 되려면 첫 번째 인수가 정확히 1 이어야 하고, 남는 것은 n = 1과 n = 19 — 그 소수 41과 761의 합이 (E) 802이다.

몇 개 대입해 보기
숨어 있는 제곱의 차 찾기
인수분해하고 항등식 확인하기
큰 인수의 하한 잡기
작은 인수를 1로 강제하기
살아남는 입력 구하기
두 후보를 검증하고 더하기