AMC 8 · 2005 · #24

학년 6 arithmetic

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)

보기 방식:

도구 + 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)

비슷한 유형 더 풀어보기