AMC 10 · 2012 · #24

학년 8 number-theory

유형 Branching State Enumeration └ 세부 유형 Rule-Governed Process Simulation

prime-factorizationdivisibility-rulesrecursive-sequenceinvariant-monovariant easier-related-problemidentify-subproblemssystematic-enumeration ↑ 선수 지식: prime-factorizationrecursive-sequence

📏 긴 풀이 💡 4 개 인사이트

문제

어떤 규칙이 각 소수 거듭제곱을 바꿔 쓰고 그것을 거듭 적용한다. 출력이 끝없이 커지는 시작값의 수를 세어라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 더 쉬운 문제로 줄이기

400개의 시작값을 손으로 다 시험하는 것은 불가능하므로, 문제를 유한하고 기계적인 크기로 줄인다(도구 #9). 줄이는 방법은 두 가지다. 첫째, 지수가 1인 소수는 출력에서 사라지므로 N 중 모든 지수가 2 이상인 부분만 의미가 있다(도구 #7). 둘째, 가장 큰 소인수는 그 값이 5 이상인 동안 반드시 줄어들므로, 모든 수열은 결국 2^a3^b 꼴의 작은 세계 안으로 들어간다(도구 #14, 극단에 있는 소수를 추적). 그 세계 안에서 지수를 a, b로 이름 붙이면(도구 #4) 규칙은 두 수에 대한 사상이 되고, 두 번 적용하면 a와 b가 완전히 분리되어 성장의 임계값이 정확히 드러난다. 마지막으로 400 이하의 유한한 후보들을 나열해 센다(도구 #2). 임계값은 양쪽 방향 모두 증명해야 한다. 임계값 위에서는 지수가 실제로 폭발하고, 아래에서는 지수가 고정된 상자 안에 갇힌다는 것을 보여야 개수가 추정이 아니라 정확한 값이 된다.

1STEP 1

N에서 두꺼운 부분만 의미가 있다

수에서 거듭된 부분만 중요하다.

p ∥ N → f₁(N)=f₁ (N/p); N 유계 아님 ⇔ R 유계 아님, R=Π_e_p ≥ 2p^e_p

2STEP 2

큰 소수는 밀려 내려가 사라진다

큰 소수는 밀려 내려가 사라진다.

P(n) ≥ 5 → P(f₁(n)) ＜ P(n), 왜냐하면 q ∣ p+1, p 홀수 → q ≤ (p+1)/2

3STEP 3

2,3의 세계에서 규칙은 두 수의 사상

남는 것은 단순한 두 수의 사상이다.

f₁(2^a3^b) = 2²(b-1)^+ 3^(a-1)^+, T(a,b) = (2(b-1)^+, (a-1)^+), x^+=max(x,0)

4STEP 4

두 단계가 지수를 분리해 임계값을 드러낸다

두 단계가 성장의 임계값을 드러낸다.

T²(a,b)=(2(a-2)^+, (2b-3)^+); 2(a-2) ＞ a ⇔ a ≥ 5, 2b-3 ＞ b ⇔ b ≥ 4; T²(4,3)=(4,3)

5STEP 5

배수는 유계가 아님을 물려받는다

배수는 끝없는 성장을 물려받는다.

m ∣ n → f₁(m) ∣ f₁(n) → f_k(m) ∣ f_k(n) ∀ k

6STEP 6

가장 작은 시작값들을 찾는다

그러면 가장 작은 시작값의 짧은 목록이 남는다.

f₁(7³)=8²=2⁶, f₁(2⁴5²)=3³ · 6=2 · 3⁴, f₁(2³5²)=54 → 16 → 27 → 16

7STEP 7

배수를 센다

그 배수를 세면 18, 보기 (D).

12+4+1+1=18 → (D)

정답

판정 기준을 양쪽 방향으로 모두 증명했기 때문에 개수가 추정이 아니라 정확한 값이 된다. 임계값 위에서는 지수 사상 a↦ 2(a-2) 또는 b↦ 2b-3이 반드시 커지고, 아래에서는 두 사상이 감소하지 않으며 a=4, b=3을 고정하므로 상자 a ≤ 4, b ≤ 3이 가둔다. 경계 사례가 임계값이 딱 맞음을 확인해 준다. 16=2⁴과 27=3³은 정확히 경계 위에 있어 16→ 27→ 16으로 영원히 순환하고, 32=2⁵는 곧바로 탈출한다: 32→ 81→ 64→ 243→ 256. 예외적인 두 시작값도 주장대로 움직인다. 343→ 64, 400→ 162→ 64로 모두 임계값을 넘은 2의 거듭제곱에 도달하는 반면, 아슬아슬하게 빗나가는 200=2³5²은 200→ 54→ 16이 되어 순환에 갇힌다. 서로 겹치지 않는 네 묶음을 다시 더해도 12+4+1+1=18로 선택지 (D)와 일치한다. 오답 선택지들은 훑기를 빠뜨렸을 때의 함정 그대로다. 예외적인 두 수를 모두 놓치면 16, 하나만 놓치면 17이 된다.

💡핵심 정리

큰 소수는 줄어들어 사라지고 결국 2와 3만 남는데, 어떤 항이 2⁵ 또는 3⁴을 품는 순간 수열이 폭발한다. 그래서 32, 81, 343, 400의 배수를 세면 12+4+1+1=18.

N에서 두꺼운 부분만 의미가 있다
큰 소수는 밀려 내려가 사라진다
2,3의 세계에서 규칙은 두 수의 사상
두 단계가 지수를 분리해 임계값을 드러낸다
배수는 유계가 아님을 물려받는다
가장 작은 시작값들을 찾는다
배수를 센다