AMC 8 · 2020 · #22

학년 4 number-theorylogic

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

parityrecursive-sequencedivisibility-rulesfunction-evaluation tree-enumerationcaseworksystematic-enumeration ↑ 선수 지식: parityfunction-evaluation

📏 긴 풀이 💡 4 개 인사이트 📊 도형

📘 쉬운 버전 보기 →

문제

양의 정수 N을 입력하면 기계는 N이 짝수일 때

\frac{N}{2}

를, 홀수일 때 3N+1을 출력합니다. 예시로 7 → 22 → 11 → 34 → 17 → 52 → 26 처럼 규칙을 6번 연달아 적용합니다. 이 6단계 과정을 마쳤을 때 결과가 1이 되는 모든 시작값 N을 찾아 그 합을 구하는 문제입니다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 8 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 거꾸로 풀기

끝값(1)은 주어졌고 시작값(N)을 찾아야 하니, 정확히 도구 #11(거꾸로 풀기) 의 전형적 신호입니다. 기계의 역연산을 정리해 보면, 출력 O의 이전 값은 (1) 항상 짝수 분기로 2O, (2) 홀수 분기로 $\frac{O-1}{3}$ — 단, O-1이 3으로 나누어떨어지고 그 몫이 양의 홀수일 때만 — 두 종류입니다. 매 역단계마다 후보가 갈라질 수 있으므로 도구 #2(빠짐없이 나열하기) 로 트리의 가지를 빠짐없이·중복없이 적습니다. 도구 #7(작은 문제로 쪼개기) 은 "X의 모든 이전 값 찾기"라는 작은 부분문제를 정의해 매 단계 똑같이 반복할 수 있게 해 줍니다.

1STEP 1

기계를 뒤집으면, 출력 O의 이전 값은 2O(항상 유효) 또는 몫이 양의 홀수일 때만 유효한 $\frac{O-1}{3}$ 입니다.

이전값(O) = { 2O } ∪ {

\frac{O-1}{3}

: 3 ∣ (O-1),

\frac{O-1}{3}

가 양의 홀수 }

2STEP 2

1의 이전 값은 2 하나뿐 (홀수 분기는 0이라 무효).

이전값(1) = {2}

3STEP 3

2의 이전 값은 4 하나뿐 (홀수 분기 $\frac{1}{3}$ 은 정수 아님).

이전값(2) = {4}

4STEP 4

4의 이전 값은 1과 8 — 홀수 분기 $\frac{4-1}{3}$ =1이 살아나 트리가 갈라집니다.

이전값(4) = {1, 8}

5STEP 5

{1, 8}의 이전 값은 2와 16 (8의 홀수 분기 $\frac{7}{3}$ 은 무효).

이전값({1,8}) = {2, 16}

6STEP 6

{2, 16}의 이전 값은 4, 5, 32 — 16의 홀수 분기 $\frac{16-1}{3}$ =5가 유효.

이전값({2,16}) = {4, 5, 32}

7STEP 7

마지막 역단계로 시작값 1, 8, 10, 64를 얻습니다 (5와 32의 홀수 분기는 무효).

N ∈ {1, 8, 10, 64}

8STEP 8

네 시작값 1 + 8 + 10 + 64를 더하면 83, 선택지 (E).

1 + 8 + 10 + 64 = 83 → (E)

정답

N = 10 으로 검산: 10 → 5 → 16 → 8 → 4 → 2 → 1 — 정확히 6단계 만에 1. N = 64 로 검산: 64 → 32 → 16 → 8 → 4 → 2 → 1 — 역시 6단계. 나머지 N = 1, 8 도 1 → 4 → 2 → 1 사이클을 거쳐 6단계째에 1로 떨어집니다. 유효한 네 값의 합 83이 선택지 (E)와 일치하고, 다른 선택지 중에서 ≡ 2 (mod 3) 인 것은 (E) 하나뿐 — 홀수 분기 한 번이 3의 배수에 1을 더한 형태를 만들기 때문에 직관과도 부합합니다.

💡핵심 정리

이 AMC 8 문제는 사실 4학년 때 배운 곱셈·3으로 나누어떨어지는지 확인하기·덧셈만 알면 풀 수 있어요 — 거기에 "거꾸로 풀기"라는 강력한 전략 하나만 더하면 됩니다!

비슷한 유형 더 풀어보기