AMC 8 · 2005 · #24

학년 6 arithmetic

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

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

📏 긴 풀이 💡 4 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 거꾸로 풀기

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

1STEP 1

거꾸로 풉니다: [+1] 의 역은 [-1], [× 2] 의 역은 [÷ 2]. 절반이 빼기보다 빠르니 짝수면 나누고 홀수면 1 빼기.

짝수 n → n ÷ 2, 홀수 n → n - 1

2STEP 2

200 에서 규칙을 적용해 내려갑니다: 200, 100, 50, 25, 24, 12, 6, 3, 2, 1 — 9 번 만에 1 에 도달.

단계 & 값 & 사용 키 ; 0 & 200 & 시작 ; 1 & 100 & ÷ 2 ; 2 & 50 & ÷ 2 ; 3 & 25 & ÷ 2 ; 4 & 24 & -1 ; 5 & 12 & ÷ 2 ; 6 & 6 & ÷ 2 ; 7 & 3 & ÷ 2 ; 8 & 2 & -1 ; 9 & 1 & ÷ 2 ;

3STEP 3

경로를 뒤집습니다: [÷ 2] 는 [× 2] 로, [-1] 은 [+1] 로. 정방향 경로 1→2→3→6→12→24→25→50→100→200.

1 → 2 → 3 → 6 → 12 → 24 → 25 → 50 → 100 → 200

4STEP 4

왜 더 적을 수 없을까요? [× 2] 만 쓰면 k 번에 2^k, 2⁷ = 128 ＜ 200 ＜ 256 = 2⁸ 이라 200 에 못 미칩니다.

2⁷ = 128 ＜ 200 ＜ 256 = 2⁸ → 두 배 만들기는 최소 8 번 필요

5STEP 5

9 번짜리 경로는 있고 더 짧은 경로는 없으므로, 최소 키 입력 횟수는 9 입니다.

최소 키 입력 수 = 9 → (B)

정답

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

💡핵심 정리

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

비슷한 유형 더 풀어보기