AMC 10 · 2015 · #18

학년 8 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Answer-Choice Plug-In

prime-factorizationlinear-diophantineparity work-backwardsextreme-principle ↑ 선수 지식: prime-factorizationprime-numbers

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 함수가 합성수의 소인수를 중복까지 세어 모두 더한다. 그 함수가 만드는 값의 집합을 밝혀라.

답을 골라 클릭하세요.

(A)

the set of positive integers

(B)

the set of composite positive integers

(C)

the set of even positive integers

(D)

the set of integers greater than 3

(E)

the set of integers greater than 4

풀이 과정

전략 거꾸로 풀기

선택지들이 서로 겹치는 집합이므로 목표는 집합의 상등이고, 집합의 상등은 양쪽 포함을 모두 보여야 합니다. 도구 #15(다르게 정리하기)가 두 방향 모두를 손에 잡히게 만드는 재구성을 줍니다: 각 합성수 n 에 r 이 무엇을 하는지 묻는 대신, 어떤 정수가 소수 두 개 이상의 합으로 쓰이는지를 묻습니다. 그러면 도구 #14(극단의 원리)가 가능한 가장 작은 합을 못 박아 한쪽 방향을 끝냅니다. 도구 #11(거꾸로 풀기)은 반대 방향을 반대 순서로 끝냅니다: 목표값에서 출발해 그 값을 내놓는 합성수를 직접 만들고, 도구 #4(변수 도입하기)로 모든 짝수 목표를 덮는 식 하나와 모든 홀수 목표를 덮는 식 하나를 씁니다. 정확한 집합이 밝혀진 다음에야 도구 #3(가능성 지우기)을 씁니다 — 그리고 이때는 우연히 맞는지가 아니라, 각 선택지에서 어느 쪽으로든 빠지거나 남는 원소가 있는지를 검사합니다.

1STEP 1

r 을 소수의 합으로 바꾸기

그 함수는 소수의 단순한 합이다.

n = p₁ p₂ … p_k (k ≥ 2) ⟹ r(n) = p₁ + p₂ + … + p_k

2STEP 2

4 미만은 나올 수 없다

4 미만은 결코 나올 수 없다.

r(n) = p₁ + … + p_k ≥ 2 + … + 2_k ≥ 2 ≥ 4, r(4) = 2 + 2 = 4

3STEP 3

모든 짝수 목표에 도달하기

2의 거듭제곱이 모든 짝수 목표에 닿는다.

m = 2a, a ≥ 2: n = 2^a, r(2^a) = 2 + … + 2_a = 2a = m

4STEP 4

모든 홀수 목표에 도달하기

인수 하나를 더하면 모든 홀수에 닿는다.

m = 3 + 2b, b ≥ 1: n = 3 · 2^b, r(3 · 2^b) = 3 + 2 + … + 2_b = 3 + 2b = m

5STEP 5

양쪽 포함을 닫기

양쪽 포함이 닫힌다.

range(r) ⊆ T 그리고 T ⊆ range(r) ⟹ range(r) = T = {4, 5, 6, 7, …}

6STEP 6

다섯 집합을 양방향으로 검사하기

그것이 집합 하나를 정확히 지목한다, 보기 (D).

1 ∉ range → (A); 5 ∈ range → (B), (C); 4 ∈ range → (E); range = {m : m ＞ 3} → (D)

정답

3보다 큰 정수의 집합

출력을 손으로 만들어 보며 아래쪽이 끊기지 않는지 확인합니다: r(4) = 4, r(6) = 5, r(8) = 6, r(10) = 7, r(15) = 8, r(14) = 9, r(21) = 10, r(28) = 11, r(50) = 12 — 4 이상 모든 정수가 나타나고, 4 미만 값을 내놓는 합성수는 없습니다. 두 구성법도 이 표본들과 맞습니다: 6 = r(2³) = r(8), 9 = r(3 · 2³) = r(24)이고 실제로 24 = 2 · 2 · 2 · 3의 합은 9입니다. 선택지들이 서로 포함 관계라는 점도 운이 아니라 정면으로 처리됩니다: (E) ⊂ (D)는 오직 4 에서만 갈리는데 4가 출력이므로, 갈리는 바로 그 지점에서 (D)가 (E)를 이깁니다. (B)와 (C)는 합성수도 짝수도 아닌 단 하나의 출력 5 때문에 함께 무너집니다.

💡핵심 정리

합성수는 소수를 적어도 둘 곱한 것이므로 가장 작은 합은 2 + 2 = 4이고, 그다음부터는 2를 쌓아 모든 짝수를, 3 하나를 더해 모든 홀수를 맞출 수 있으니 3 보다 큰 정수는 전부 나오고 그 아래는 하나도 나오지 않습니다.

r 을 소수의 합으로 바꾸기
4 미만은 나올 수 없다
모든 짝수 목표에 도달하기
모든 홀수 목표에 도달하기
양쪽 포함을 닫기
다섯 집합을 양방향으로 검사하기