경시 · AMC 대비 · 4단계 중 4

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 에서 규칙을 적용해 내려갑니다: 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 ;

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

200에서 계산기를 거꾸로 돌려 — 수가 짝수이면 항상 반으로 나누고 홀수일 때만 1을 빼면 — 1까지 내려가는 가장 짧은 길을 따라간다.

▸ 왜?

200에서 거꾸로 찾는 것은 앞으로 가는 원래 문제를 그대로 대신한다: 앞으로 누르는 각 키에는 그것을 정확히 되돌리는 역연산이 하나씩 있고, 가장 짧은 역방향 경로는 가장 짧은 정방향 경로와 한 걸음씩 짝을 이룬다.

▸ 왜?

반으로 나누기는 두 배를 되돌리고 1 빼기는 1 더하기를 되돌린다. 나눗셈은 곱셈을, 뺄셈은 덧셈을 거꾸로 하기 때문이다.

역연산뺄셈은 덧셈을, 나눗셈은 곱셈을 되돌린다 — 서로를 거꾸로 한다.

▸ 왜?

각 역방향 걸음은 정방향 걸음 하나와 딱 짝지어졌다가 되돌아오므로, 올라가는 길과 내려가는 길은 언제나 걸음 수가 같다.

일대일 대응여기 있는 것 하나가 저기 있는 것 하나와 딱 짝지어지면 두 무리의 크기는 같다.

▸ 왜?

허용된 두 이동 중에서 반으로 나누기를 매번 우선해야 한다. 1을 빼는 것보다 수를 훨씬 빠르게 줄이기 때문이다.

▸ 왜?

두 배는 수를 자기 자신에 더해 만든 것이라, 그 역인 반으로 나누기는 한 번에 값의 절반을 통째로 걷어낸다. 반면 1 빼기는 단 하나만 벗겨낼 뿐이다.

곱셈은 같은 크기 묶음a 곱하기 b는 b가 든 같은 묶음 a개 — 같은 양을 반복해서 더하는 것이다.

▸ 왜?

반으로 나누기는 수가 짝수일 때만 허용된다. 짝수는 정확히 같은 크기의 두 정수 묶음이라 깔끔하게 둘로 갈라지지만, 홀수는 정수 절반으로 나뉘지 않기 때문이다.

곱셈은 같은 크기 묶음a 곱하기 b는 b가 든 같은 묶음 a개 — 같은 양을 반복해서 더하는 것이다.

4.OA.C.5Work Backwards

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 번이 정말 최솟값임이 확인됩니다.

거꾸로 규칙 세우기
200부터 거꾸로 가기
경로 뒤집어 순서 만들기
더 짧은 길 없는지 따지기
답 읽어 내기

가족의 부모 대시보드는 sensimlab.com에 있습니다.

거꾸로 규칙 세우기

200부터 거꾸로 가기

경로 뒤집어 순서 만들기

더 짧은 길 없는지 따지기

답 읽어 내기

비슷한 유형 더 풀어보기