AMC 8 · 2020 · #22

학년 4 number-theorylogic

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

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

📘 쉬운 버전 보기 →

문제

양의 정수 $N$ 을 한 기계에 넣으면, 아래에 표시된 규칙에 따라 계산된 수가 출력됩니다.

예를 들어, $N=7$ 을 입력하여 시작하면, 기계는 $3 \cdot 7 + 1 = 22$ 를 출력합니다. 그 출력을 다시 기계에 다섯 번 더 반복해서 넣으면, 최종 출력은 $26$ 이 됩니다. $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ 같은 $6$ 단계 과정을 다른 시작 값 $N$ 에 적용했을 때, 최종 출력이 $1$ 이 되었습니다. 이러한 모든 정수 $N$ 의 합은 얼마입니까? $N \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to 1$
$\textbf{(A) }73 \qquad \textbf{(B) }74 \qquad \textbf{(C) }75 \qquad \textbf{(D) }82 \qquad \textbf{(E) }83$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

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

주어진 것: 규칙: $N$이 짝수이면 $N/2$, 홀수이면 $3N+1$을 출력; 예시 사슬: $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ (총 6단계); 우리 문제에서는 $N \to \square \to \square \to \square \to \square \to \square \to 1$, 즉 6단계 후 결과가 $1$; $N$은 양의 정수여야 함; 선택지: (A) $73$, (B) $74$, (C) $75$, (D) $82$, (E) $83$

구하는 것: 6단계 과정의 결과가 $1$이 되는 모든 양의 정수 $N$의 합

이해

계획

주요 도구: #11 거꾸로 풀기

보조 도구: #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기

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

실행 — 정답: E

#11 거꾸로 풀기 4.OA.B.4 단계 1

기계를 역연산으로 바꿉니다.
출력이 $O$일 때 입력 후보는 (짝수 분기) $2O$ — 항상 짝수라서 언제나 유효 — 와 (홀수 분기) $(O-1)/3$ — $O-1$이 $3$으로 나누어떨어지고 그 몫이 양의 홀수일 때만 유효 — 두 가지입니다.

$$\text{이전값}(O) = \{\,2O\,\} \cup \{\,(O-1)/3 : 3 \mid (O-1),\;(O-1)/3 \text{ 가 양의 홀수}\,\}$$

💡 "어떤 값이 이 출력을 만들었을까?"라고 묻는 역연산 발상이고, $3$으로 나누어떨어지는지 검사하는 부분이 4학년 배수·약수 표준에 정확히 닿습니다.

#11 거꾸로 풀기 3.OA.A.3 단계 2

$1$의 이전 값을 구합니다.
짝수 분기: $2 \times 1 = 2$ (유효).
홀수 분기: $(1-1)/3 = 0$, 양의 홀수가 아니므로 무효.
따라서 5단계 후 값은 $2$ 하나뿐입니다.

$$\text{이전값}(1) = \{2\}$$

💡 $1$을 두 배 하고 나누어떨어지는지 보는 것은 3학년 곱셈·나눗셈 수준의 계산입니다.

#11 거꾸로 풀기 3.OA.A.3 단계 3

$2$의 이전 값을 구합니다.
짝수 분기: $2 \times 2 = 4$ (유효).
홀수 분기: $(2-1)/3 = 1/3$, 정수가 아니므로 무효.
4단계 후 값은 $4$ 하나입니다.

$$\text{이전값}(2) = \{4\}$$

💡 같은 절차를 다시 한 번 — 두 배 하기와 나누어떨어짐 검사.

#2 빠짐없이 나열하기 4.OA.B.4 단계 4

$4$의 이전 값을 구합니다.
짝수 분기: $2 \times 4 = 8$ (유효).
홀수 분기: $(4-1)/3 = 1$ — 양의 홀수이므로 유효.
여기서부터 트리가 갈라져, 3단계 후 값은 $1$ 또는 $8$입니다.

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

💡 분기가 생기는 순간부터는 작은 값부터 차례로 적는 식의 "순서 규칙"을 두어야 빠뜨림이 없습니다 — 도구 #2의 핵심 습관입니다.

#7 작은 문제로 쪼개기 4.OA.B.4 단계 5

$\{1, 8\}$ 각각의 이전 값을 구합니다.
$1$의 이전 값은 이미 본 대로 $\{2\}$.
$8$의 짝수 분기: $16$ (유효), 홀수 분기: $(8-1)/3 = 7/3$ — 정수가 아니므로 무효.
둘을 합치면 2단계 후 값은 $\{2, 16\}$ 입니다.

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

💡 "$X$의 모든 이전 값 구하기"가 매 노드마다 똑같이 반복되는 작은 부분문제 — 도구 #7의 발상.

#2 빠짐없이 나열하기 4.OA.B.4 단계 6

$\{2, 16\}$ 각각의 이전 값을 구합니다.
$2$의 이전 값은 $\{4\}$.
$16$의 짝수 분기: $32$ (유효), 홀수 분기: $(16-1)/3 = 5$ — 양의 홀수이므로 유효.
1단계 후 값은 $\{4,\,5,\,32\}$ 입니다.

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

💡 $16 - 1 = 15$가 $3$의 배수이므로 홀수 분기가 살아납니다 — 4학년 배수 판정 그대로.

#2 빠짐없이 나열하기 4.OA.A.3 단계 7

마지막으로 $\{4, 5, 32\}$ 의 이전 값을 구해 $N$을 얻습니다.
$4$의 이전 값은 $\{1, 8\}$ (앞에서 계산).
$5$의 짝수 분기: $10$ (유효), 홀수 분기: $(5-1)/3 = 4/3$ (정수 아님).
$32$의 짝수 분기: $64$ (유효), 홀수 분기: $(32-1)/3 = 31/3$ (정수 아님).
따라서 $N \in \{1, 8, 10, 64\}$.

$$N \in \{1,\,8,\,10,\,64\}$$

💡 여섯 번의 역단계 동안 모든 가지를 따라가는 것은 4학년 수준의 "네 가지 연산을 쓰는 다단계 문제" 그 자체입니다.

#11 거꾸로 풀기 4.NBT.B.4 단계 8

유효한 시작값 네 개의 합을 구합니다.

$$1 + 8 + 10 + 64 = 83 \;\Rightarrow\; \textbf{(E)}$$

💡 두 자리 정도의 수 몇 개를 더하는 것은 4학년 다자리 덧셈으로 충분합니다.

[1] #11 4.OA.B.4 기계를 역연산으로 바꿉니다. 출력이 $O$일 때 입력 후보는 (짝수 분기) $2O$ — 항상 짝수라서 언제나 유효 — 와 (홀수 분기) $(O-

[2] #11 3.OA.A.3 $1$의 이전 값을 구합니다. 짝수 분기: $2 \times 1 = 2$ (유효). 홀수 분기: $(1-1)/3 = 0$, 양의 홀수가 아니므로

[3] #11 3.OA.A.3 $2$의 이전 값을 구합니다. 짝수 분기: $2 \times 2 = 4$ (유효). 홀수 분기: $(2-1)/3 = 1/3$, 정수가 아니므로

[4] #2 4.OA.B.4 $4$의 이전 값을 구합니다. 짝수 분기: $2 \times 4 = 8$ (유효). 홀수 분기: $(4-1)/3 = 1$ — 양의 홀수이므로 유

[5] #7 4.OA.B.4 $\{1, 8\}$ 각각의 이전 값을 구합니다. $1$의 이전 값은 이미 본 대로 $\{2\}$. $8$의 짝수 분기: $16$ (유효), 홀수

[6] #2 4.OA.B.4 $\{2, 16\}$ 각각의 이전 값을 구합니다. $2$의 이전 값은 $\{4\}$. $16$의 짝수 분기: $32$ (유효), 홀수 분기: $

[7] #2 4.OA.A.3 마지막으로 $\{4, 5, 32\}$ 의 이전 값을 구해 $N$을 얻습니다. $4$의 이전 값은 $\{1, 8\}$ (앞에서 계산). $5$의

[8] #11 4.NBT.B.4 유효한 시작값 네 개의 합을 구합니다.

검토

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

대안 접근: 도구 #1(그림 그리기) 와 잘 어울리는 문제입니다. 맨 아래에 $1$을 두고, 위로 올라가며 짝수·홀수 두 분기를 화살표로 그리되 홀수 분기가 살아 있을 때만 가지를 추가하는 식으로 6단계 트리를 그립니다. 깊이 $6$의 잎(leaf) 들이 곧 $\{1, 8, 10, 64\}$ — 그림에서 바로 읽힙니다. 트리를 먼저 그린 뒤 잎을 도구 #2로 적어 합산하는 풀이를 선호하는 학생도 많습니다.

사용된 CCSS 표준 (최저 학년 4)

3.OA.A.3 100 이내의 곱셈·나눗셈 문장제 해결 (작은 출력값에 대해 $2$를 곱해 짝수 이전 값을 구하거나($2 \times 1$, $2 \times 2$), $(O-1)/3$이 정수인지 따져보는 기초 계산.)
4.OA.A.3 네 가지 연산을 사용한 다단계 정수 문장제 해결 (여섯 번의 역단계 동안 중간 값의 트리를 관리하며 모든 가지를 끝까지 따라가는 데 사용.)
4.OA.B.4 약수쌍 모두 구하기·배수 인식, 소수·합성수 판별 (각 단계에서 홀수 분기의 역연산 $(O-1)/3$ 이 유효한지 — 즉 $O-1$ 이 $3$의 배수인지 — 판정하는 데 사용.)
4.NBT.B.4 다자리 정수의 능숙한 덧셈·뺄셈 (마지막에 $1 + 8 + 10 + 64 = 83$ 의 합을 구하는 데 사용.)

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

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: E

검토

사용된 CCSS 표준 (최저 학년 4)

비슷한 유형 더 풀어보기