AMC 8 · 2020 · #22
학년 4 number-theorylogic문제
양의 정수 N을 한 기계에 넣으면, 아래에 표시된 규칙에 따라 계산된 수가 출력됩니다.
예를 들어, N=7을 입력하여 시작하면, 기계는 3⋅7+1=22를 출력합니다. 그 출력을 다시 기계에 다섯 번 더 반복해서 넣으면, 최종 출력은 26이 됩니다.7→22→11→34→17→52→26같은 6단계 과정을 다른 시작 값 N에 적용했을 때, 최종 출력이 1이 되었습니다. 이러한 모든 정수 N의 합은 얼마입니까?N→→→→→→1
답을 골라 클릭하세요.
AMC 8 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + 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$의 합
이해
문제 재정리: 양의 정수 $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$
계획
주요 도구: #11 거꾸로 풀기
보조 도구: #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기
끝값($1$)은 주어졌고 시작값($N$)을 찾아야 하니, 정확히 도구 #11(거꾸로 풀기) 의 전형적 신호입니다. 기계의 역연산을 정리해 보면, 출력 $O$의 이전 값은 (1) 항상 짝수 분기로 $2O$, (2) 홀수 분기로 $(O-1)/3$ — 단, $O-1$이 $3$으로 나누어떨어지고 그 몫이 양의 홀수일 때만 — 두 종류입니다. 매 역단계마다 후보가 갈라질 수 있으므로 도구 #2(빠짐없이 나열하기) 로 트리의 가지를 빠짐없이·중복없이 적습니다. 도구 #7(작은 문제로 쪼개기) 은 "$X$의 모든 이전 값 찾기"라는 작은 부분문제를 정의해 매 단계 똑같이 반복할 수 있게 해 줍니다.
실행 — 정답: E
4.OA.B.4 단계 1 - 기계를 역연산으로 바꿉니다.
- 출력이 $O$일 때 입력 후보는 (짝수 분기) $2O$ — 항상 짝수라서 언제나 유효 — 와 (홀수 분기) $(O-1)/3$ — $O-1$이 $3$으로 나누어떨어지고 그 몫이 양의 홀수일 때만 유효 — 두 가지입니다.
💡 "어떤 값이 이 출력을 만들었을까?"라고 묻는 역연산 발상이고, $3$으로 나누어떨어지는지 검사하는 부분이 4학년 배수·약수 표준에 정확히 닿습니다.
3.OA.A.3 단계 2 - $1$의 이전 값을 구합니다.
- 짝수 분기: $2 \times 1 = 2$ (유효).
- 홀수 분기: $(1-1)/3 = 0$, 양의 홀수가 아니므로 무효.
- 따라서 5단계 후 값은 $2$ 하나뿐입니다.
💡 $1$을 두 배 하고 나누어떨어지는지 보는 것은 3학년 곱셈·나눗셈 수준의 계산입니다.
3.OA.A.3 단계 3 - $2$의 이전 값을 구합니다.
- 짝수 분기: $2 \times 2 = 4$ (유효).
- 홀수 분기: $(2-1)/3 = 1/3$, 정수가 아니므로 무효.
- 4단계 후 값은 $4$ 하나입니다.
💡 같은 절차를 다시 한 번 — 두 배 하기와 나누어떨어짐 검사.
4.OA.B.4 단계 4 - $4$의 이전 값을 구합니다.
- 짝수 분기: $2 \times 4 = 8$ (유효).
- 홀수 분기: $(4-1)/3 = 1$ — 양의 홀수이므로 유효.
- 여기서부터 트리가 갈라져, 3단계 후 값은 $1$ 또는 $8$입니다.
💡 분기가 생기는 순간부터는 작은 값부터 차례로 적는 식의 "순서 규칙"을 두어야 빠뜨림이 없습니다 — 도구 #2의 핵심 습관입니다.
4.OA.B.4 단계 5 - $\{1, 8\}$ 각각의 이전 값을 구합니다.
- $1$의 이전 값은 이미 본 대로 $\{2\}$.
- $8$의 짝수 분기: $16$ (유효), 홀수 분기: $(8-1)/3 = 7/3$ — 정수가 아니므로 무효.
- 둘을 합치면 2단계 후 값은 $\{2, 16\}$ 입니다.
💡 "$X$의 모든 이전 값 구하기"가 매 노드마다 똑같이 반복되는 작은 부분문제 — 도구 #7의 발상.
4.OA.B.4 단계 6 - $\{2, 16\}$ 각각의 이전 값을 구합니다.
- $2$의 이전 값은 $\{4\}$.
- $16$의 짝수 분기: $32$ (유효), 홀수 분기: $(16-1)/3 = 5$ — 양의 홀수이므로 유효.
- 1단계 후 값은 $\{4,\,5,\,32\}$ 입니다.
💡 $16 - 1 = 15$가 $3$의 배수이므로 홀수 분기가 살아납니다 — 4학년 배수 판정 그대로.
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\}$.
💡 여섯 번의 역단계 동안 모든 가지를 따라가는 것은 4학년 수준의 "네 가지 연산을 쓰는 다단계 문제" 그 자체입니다.
4.NBT.B.4 단계 8 유효한 시작값 네 개의 합을 구합니다.
💡 두 자리 정도의 수 몇 개를 더하는 것은 4학년 다자리 덧셈으로 충분합니다.
4.OA.B.4 기계를 역연산으로 바꿉니다. 출력이 $O$일 때 입력 후보는 (짝수 분기) $2O$ — 항상 짝수라서 언제나 유효 — 와 (홀수 분기) $(O- 3.OA.A.3 $1$의 이전 값을 구합니다. 짝수 분기: $2 \times 1 = 2$ (유효). 홀수 분기: $(1-1)/3 = 0$, 양의 홀수가 아니므로 3.OA.A.3 $2$의 이전 값을 구합니다. 짝수 분기: $2 \times 2 = 4$ (유효). 홀수 분기: $(2-1)/3 = 1/3$, 정수가 아니므로 4.OA.B.4 $4$의 이전 값을 구합니다. 짝수 분기: $2 \times 4 = 8$ (유효). 홀수 분기: $(4-1)/3 = 1$ — 양의 홀수이므로 유 4.OA.B.4 $\{1, 8\}$ 각각의 이전 값을 구합니다. $1$의 이전 값은 이미 본 대로 $\{2\}$. $8$의 짝수 분기: $16$ (유효), 홀수 4.OA.B.4 $\{2, 16\}$ 각각의 이전 값을 구합니다. $2$의 이전 값은 $\{4\}$. $16$의 짝수 분기: $32$ (유효), 홀수 분기: $ 4.OA.A.3 마지막으로 $\{4, 5, 32\}$ 의 이전 값을 구해 $N$을 얻습니다. $4$의 이전 값은 $\{1, 8\}$ (앞에서 계산). $5$의 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.3100 이내의 곱셈·나눗셈 문장제 해결 (작은 출력값에 대해 $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$으로 나누어떨어지는지 확인하기·덧셈만 알면 풀 수 있어요 — 거기에 "거꾸로 풀기"라는 강력한 전략 하나만 더하면 됩니다!
⭐ 이 AMC 8 문제는 사실 4학년 때 배운 곱셈·$3$으로 나누어떨어지는지 확인하기·덧셈만 알면 풀 수 있어요 — 거기에 "거꾸로 풀기"라는 강력한 전략 하나만 더하면 됩니다!
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.
