AMC 8 · 2005 · #24

학년 6 arithmetic

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

optimization-countingparityrecursive-sequencesystematic-enumeration optimization-countingtree-enumeration ↑ 선수 지식: paritysystematic-enumeration

📏 긴 풀이 💡 4 개 인사이트

문제

A certain calculator has only two keys [+1] and [x2]. When you press one of the keys, the calculator automatically displays the result. For instance, if the calculator originally displayed "9" and you pressed [+1], it would display "10." If you then pressed [x2], it would display "20." Starting with the display "1," what is the fewest number of keystrokes you would need to reach "200"?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 계산기에 키가 두 개뿐입니다: $[+1]$ ($1$ 더하기) 와 $[\times 2]$ (두 배 만들기). 화면은 $1$ 에서 시작합니다. 화면을 $200$ 으로 만들려면 최소 몇 번의 키 입력이 필요한가요?

주어진 것: 처음 화면 값 $= 1$; 사용 가능한 키: $[+1]$ 과 $[\times 2]$; 목표 화면 값 $= 200$; 선택지: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$

구하는 것: 화면을 $1$ 에서 $200$ 으로 만드는 데 필요한 최소 키 입력 횟수

이해

주어진 것: 처음 화면 값 $= 1$; 사용 가능한 키: $[+1]$ 과 $[\times 2]$; 목표 화면 값 $= 200$; 선택지: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$

계획

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

보조 도구: #9 더 쉬운 문제로 바꾸기

$1$ 에서 앞으로 진행하면 키 입력마다 두 가지 선택 ($+1$ 또는 $\times 2$) 이 생겨서 경우의 수가 폭발적으로 늘어납니다. 도구 #11(거꾸로 풀기)는 방향을 뒤집습니다: $[\times 2]$ 의 역은 $[\div 2]$ (수가 짝수일 때만 허용), $[+1]$ 의 역은 $[-1]$. $200$ 에서 $1$ 로 내려갈 때 $[\div 2]$ 는 값을 절반으로 줄이지만 $[-1]$ 은 $1$ 만 깎으므로, 가장 빠르려면 짝수일 때마다 나누고 홀수일 때만 $[-1]$ 을 써야 합니다. 그러면 역방향 경로가 한 갈래로 정해집니다. 도구 #9(더 쉬운 문제로 바꾸기) 는 "왜 더 적게는 안 되는가?" 쪽을 맡습니다. $[\times 2]$ 만 있다고 가정하면 $k$ 번의 입력은 $1$ 을 $2^k$ 로 만드는데, $2^7 = 128 < 200 < 256 = 2^8$ 이므로 가장 강한 키를 쓰더라도 $7$ 번으로는 $200$ 에 닿을 수 없습니다. 강제된 역방향 횟수와 합치면 $9$ 는 도달 가능하면서 동시에 최소값입니다.

실행 — 정답: B

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

역방향 규칙을 정합니다.
$[+1]$ 의 역은 $[-1]$, $[\times 2]$ 의 역은 $[\div 2]$.
절반으로 나누는 쪽이 $1$ 을 빼는 쪽보다 훨씬 빠르므로, 현재 값이 짝수이면 $[\div 2]$ 를 쓰고, 홀수이면 $[\div 2]$ 가 허용되지 않으므로 $[-1]$ 을 한 번 써서 짝수로 만들어야 합니다.

$$\text{짝수 } n \to n \div 2, \qquad \text{홀수 } n \to n - 1$$

💡 짝·홀 판단은 4학년의 "인수" 개념 그대로입니다 — 어떤 수가 $2$ 로 나누어떨어진다는 것은 곧 짝수라는 뜻이고, 그 짝·홀이 어떤 역연산 키를 쓸 수 있는지를 결정합니다.

#11 거꾸로 풀기 4.OA.C.5 단계 2

$200$ 에서 시작해 규칙을 적용하고, $1$ 에 도달할 때까지 키 입력 수를 셉니다.

$$\begin{array}{c|c|c} \text{단계} & \text{값} & \text{사용 키}\\\hline 0 & 200 & \text{시작}\\ 1 & 100 & \div 2\\ 2 & 50 & \div 2\\ 3 & 25 & \div 2\\ 4 & 24 & -1\\ 5 & 12 & \div 2\\ 6 & 6 & \div 2\\ 7 & 3 & \div 2\\ 8 & 2 & -1\\ 9 & 1 & \div 2\\ \end{array}$$

💡 정해진 규칙으로 이전 값에서 다음 값을 만들어내는 것은 4학년 "규칙에 따라 수의 패턴 만들기" 그대로입니다. 규칙 적용 $9$ 번으로 $200$ 에서 $1$ 까지 내려옵니다.

#11 거꾸로 풀기 4.OA.C.5 단계 3

역방향 경로를 뒤집어서 $1$ 에서 $200$ 으로 가는 정방향 키 입력 순서를 얻습니다.
$[\div 2]$ 는 모두 $[\times 2]$ 로, $[-1]$ 은 모두 $[+1]$ 로 바뀝니다.

$$1 \xrightarrow{\times 2} 2 \xrightarrow{+1} 3 \xrightarrow{\times 2} 6 \xrightarrow{\times 2} 12 \xrightarrow{\times 2} 24 \xrightarrow{+1} 25 \xrightarrow{\times 2} 50 \xrightarrow{\times 2} 100 \xrightarrow{\times 2} 200$$

💡 길이 $9$ 의 역방향 경로는 그대로 길이 $9$ 의 정방향 경로가 됩니다 — 같은 화살표를 방향만 뒤집은 것이죠.

#9 더 쉬운 문제로 바꾸기 6.EE.A.1 단계 4

더 짧은 경로는 불가능함을 보입니다.
$[\times 2]$ 만 있는 더 쉬운 문제를 생각합시다.
$k$ 번 입력하면 화면은 $2^k$ 가 됩니다.
$2^7 = 128 < 200$ 이므로 가장 강력한 키만 $7$ 번 눌러도 $200$ 에 닿을 수 없습니다.
실제 (평균적으로 더 약한) 규칙에서는 $8$ 번 미만으로도 불가능합니다.
그리고 $8$ 번을 모두 $[\times 2]$ 로 채우면 정확히 $2^8 = 256$ 에 떨어지므로 $200$ 에는 닿지 못합니다.
따라서 최소 횟수는 적어도 $9$ 이고, 우리가 찾은 길이 $9$ 의 경로가 그 값을 실제로 달성합니다.

$$2^7 = 128 < 200 < 256 = 2^8 \;\Rightarrow\; \text{두 배 만들기는 최소 } 8 \text{ 번 필요}$$

💡 규칙을 "두 배만 가능" 이라는 더 단순한 규칙으로 바꾸면 6학년 자연수 지수를 이용한 깔끔한 하한이 나옵니다 — 그 하한과 짝·홀 논리를 합치면 $9$ 가 강제됩니다.

#11 거꾸로 풀기 4.OA.C.5 단계 5

답을 정리합니다.
길이 $9$ 의 경로는 존재하고, 더 짧은 경로는 존재하지 않으므로 최소 키 입력 횟수는 $9$ 입니다.

$$\text{최소 키 입력 수} = 9 \;\Rightarrow\; \textbf{(B)}$$

💡 역방향 탐색으로 "가능한가?" 를 보이고, 하한 확인으로 "더 줄일 수 있는가?" 를 막으면 답이 그 사이에 한 점으로 고정됩니다.

[1] #11 4.OA.B.4 역방향 규칙을 정합니다. $[+1]$ 의 역은 $[-1]$, $[\times 2]$ 의 역은 $[\div 2]$. 절반으로 나누는 쪽이 $1$

[2] #11 4.OA.C.5 $200$ 에서 시작해 규칙을 적용하고, $1$ 에 도달할 때까지 키 입력 수를 셉니다.

[3] #11 4.OA.C.5 역방향 경로를 뒤집어서 $1$ 에서 $200$ 으로 가는 정방향 키 입력 순서를 얻습니다. $[\div 2]$ 는 모두 $[\times 2]$

[4] #9 6.EE.A.1 더 짧은 경로는 불가능함을 보입니다. $[\times 2]$ 만 있는 더 쉬운 문제를 생각합시다. $k$ 번 입력하면 화면은 $2^k$ 가 됩니

[5] #11 4.OA.C.5 답을 정리합니다. 길이 $9$ 의 경로는 존재하고, 더 짧은 경로는 존재하지 않으므로 최소 키 입력 횟수는 $9$ 입니다.

검토

합리성 확인: 정방향 경로를 한 입력씩 따라가 보면 확인됩니다: $1, 2, 3, 6, 12, 24, 25, 50, 100, 200$. 시작값 $1$ 뒤에 화살표가 $9$ 개 — 즉 키 입력 $9$ 번 — 이고 정확히 $200$ 에 떨어집니다. 또한 이 경로는 $[\times 2]$ 를 $7$ 번, $[+1]$ 을 $2$ 번 사용하며, 두 배 만들기만으로는 $1$ 이 $2^7 = 128$ 로 커지는데 그 사이사이에 끼워 넣은 두 번의 $[+1]$ 이 값을 $200$ 까지 끌어올리는 것과 일관됩니다. 일치하는 선택지는 (B).

대안 접근: 도구 #5(패턴 찾기) — 이진법 활용. $200$ 을 이진수로 쓰면 $200 = 128 + 64 + 8 = 11001000_2$. 이진 자리를 왼쪽에서 오른쪽으로 읽을 때 각 자리는 $[\times 2]$ 한 번 (자리 이동) 과, 그 자리가 $1$ 이면 추가로 $[+1]$ 한 번이 필요합니다. 자리 수는 $8$ 개라 $[\times 2]$ 가 $8$ 번이지만, 맨 앞의 $1$ 에 해당하는 첫 자리 이동은 시작값 $1$ 자체로 대체되므로 $[\times 2]$ 하나가 절약됩니다. 따라서 전체 키 입력 수 $= (\text{자릿수} - 1) + (\text{$1$ 의 개수} - 1) = 7 + 2 = 9$. 같은 답 (B) 가 이진 표현 경로로도 얻어집니다.

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

4.OA.B.4 어떤 수의 모든 인수쌍을 찾고, 그 수가 소수인지 합성수인지 판별하기 (각 역방향 단계에서 역연산 키 $[\div 2]$ 를 쓸 수 있는지 결정하기 위해 짝·홀 ($2$ 로 나누어떨어짐) 을 사용.)
4.OA.C.5 주어진 규칙에 따른 수 또는 모양의 패턴 만들기 ("짝수면 절반, 홀수면 $1$ 빼기" 규칙을 단계마다 적용해 역방향 수열 $200, 100, 50, 25, 24, 12, 6, 3, 2, 1$ 을 만드는 데 사용.)
6.EE.A.1 자연수 지수를 포함한 수치 식을 쓰고 계산하기 ($200$ 을 $2^7 = 128$ 및 $2^8 = 256$ 과 비교해 $7$ 번이나 $8$ 번의 키 입력으로는 $200$ 에 닿을 수 없음을 보이는 데 사용.)

⭐ 계산기를 거꾸로 돌리면 이 AMC 8 문제가 4학년 "짝수면 반으로, 아니면 $1$ 빼기" 라는 패턴 규칙으로 풀리고, 6학년 $2$ 의 거듭제곱 비교로 $9$ 번이 정말 최솟값임이 확인됩니다.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기