AMC 10 · 2021 · #20

학년 9 number-theory

유형 Branching State Enumeration └ 세부 유형 Numeric Operation Tree

divisor-countfunction-compositionprime-factorizationrecursive-sequence pattern-recognitionsystematic-enumeration ↑ 선수 지식: divisor-countfunction-composition

📏 긴 풀이 💡 4 개 인사이트

문제

어떤 규칙이 수를 그 수의 양의 약수 개수의 두 배로 바꿉니다. 이 규칙을 계속 반복합니다. 1부터 50까지의 각 정수에서 시작해 규칙을 쉰 번 적용했을 때 12에서 끝나는 시작값이 몇 개인지 세세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 패턴 찾기

규칙을 손으로 50 번 적용하는 사람은 없으므로, 50 이라는 숫자는 허풍일 수밖에 없다. 그 허풍을 잡아내는 것이 도구 #5 (패턴 찾기)이다. 작은 수들의 집합 위에서 규칙을 계속 적용하면 반드시 값이 반복되는 자리로 들어가고, 규칙이 자기 자신으로 보내는 값에 도달하면 남은 단계는 아무 일도 하지 않는다. 도구 #15 (다르게 정리하기)는 두 줄짜리 재귀 정의를 기계 하나를 여러 번 돌리는 것으로 읽게 해 주고, 그래야 값이 자리를 잡는 모습이 보인다. 도구 #9 (더 쉬운 문제로 줄이기)는 작업량을 줄인다. 한 번만 적용해도 값이 열 개 안으로 갇히므로, 어려워 보이는 50 단계 문제가 작은 수 열 개에 대한 문제로 바뀐다. 도구 #2 (빠짐없이 나열하기)로 두 가지 정리를 한다 — 그 열 개 위에서의 규칙 표, 그리고 마지막에 약수 개수별로 n 을 나열하는 일이다. 도구 #3 (가능성 지우기)은 엉뚱한 값에 자리 잡는 사슬을 모두 버린다. 그다음 도구 #11 (거꾸로 풀기)로 첫 단계를 되돌려, 살아남은 조건을 n 에 대한 단순한 조건으로 옮긴다.

1STEP 1

반복되는 규칙 하나에 이름 붙이기

반복되는 규칙에 이름을 붙입니다.

g(m) = 2d(m), f₅₀(n) = g(g(… g(n)…))₅₀ times, g(m) is always even

2STEP 2

첫 단계가 떨어지는 범위 좁히기

첫 단계가 한 걸음 만에 작아집니다.

n ≤ 50 ⟹ d(n) ≤ 10 ⟹ f₁(n) ∈ {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

3STEP 3

제자리에 붙는 값 찾기

제자리에 붙는 값을 찾습니다.

g(8) = 2d(8) = 2 · 4 = 8, g(12) = 2d(12) = 2 · 6 = 12

4STEP 4

열 개의 수 위에서 규칙 표 만들기

열 개의 수 위에서 규칙을 표로 만듭니다.

2 → 4, 4 → 6, 6 → 8, 8 → 8, 10 → 8, 12 → 12, 14 → 8, 16 → 10, 18 → 12, 20 → 12

5STEP 5

각 사슬이 멈추는 곳 따라가기

각 사슬이 멈추는 곳을 따라갑니다.

f₅₀(n) = 12 ⇔ f₁(n) ∈ {12, 18, 20}

6STEP 6

거꾸로 약수 개수로 옮기기

거꾸로 약수 개수로 옮깁니다.

2d(n) ∈ {12, 18, 20} ⇔ d(n) ∈ {6, 9, 10}

7STEP 7

약수가 여섯 개인 수 세기

약수가 여섯 개인 수를 셉니다.

d(n) = 6: 32 = 2⁵ and 12, 18, 20, 28, 44, 45, 50 = p² q (8 numbers)

8STEP 8

아홉 개와 열 개를 세고 합치기

모두 합치면 10개입니다.

d(n) = 9: 36 d(n) = 10: 48 8 + 1 + 1 = 10 ⟹ (D)

정답

살아남은 열 개를 직접 확인해 보자: 12, 18, 20, 28, 32, 36, 44, 45, 48, 50. 약수 개수는 차례로 6, 6, 6, 6, 6, 9, 6, 6, 10, 6 이므로 첫 출력은 12, 12, 12, 12, 12, 18, 12, 12, 20, 12이다. 그중 여덟 개는 이미 12 라 자리를 잡았고, 18 → 12와 20 → 12는 한 단계 뒤에 도착한다. 그러니 열 개 모두 늦어도 3 단계에는 12 위에 놓이고, 50 단계에서는 당연히 그렇다. 이번에는 탈락한 수를 확인해 보자. n = 30은 d(30) = 8 이므로 사슬이 30 → 16 → 10 → 8 → 8 → … 가 되어 8에 자리 잡고, 제외된 것이 맞다. 경계 사례도 크기 제한을 뒷받침한다. 52 = 2² · 13은 약수가 정확히 6 개라 조건에 맞았겠지만 50을 넘으므로 탈락이고, 그래서 p = 2 갈래가 q = 11 에서 멈춘 것이다. 마지막으로 개수 자체가 선택지에 비추어 그럴듯하다. d(n) = 6 경우 하나만으로도 이미 8 개가 나오므로 7은 불가능했고, 나머지 두 경우가 정확히 하나씩만 보태므로 9 나 11이 아니라 10에 도달한다.

💡핵심 정리

약수 개수를 두 배 하는 규칙은 51 보다 작은 모든 시작값을 세 단계 안에 8 아니면 12에 멈추는 사슬로 보내므로, 쉰 단계짜리 질문은 사실 "50 이하의 n 중 약수가 정확히 6, 9, 10 개인 것은?" 하나이고, 그런 수는 10 개다.

반복되는 규칙 하나에 이름 붙이기
첫 단계가 떨어지는 범위 좁히기
제자리에 붙는 값 찾기
열 개의 수 위에서 규칙 표 만들기
각 사슬이 멈추는 곳 따라가기
거꾸로 약수 개수로 옮기기
약수가 여섯 개인 수 세기
아홉 개와 열 개를 세고 합치기