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

AMC 8 · 2020 · #22

학년 4 number-theorylogic

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

parityrecursive-sequencedivisibility-rulesfunction-evaluation tree-enumerationcaseworksystematic-enumeration ↑ 선수 지식: parityfunction-evaluation

📏 긴 풀이 💡 4 개 인사이트 📊 도형

📘 쉬운 버전 보기 →

문제

양의 정수 N을 입력하면 기계는 N이 짝수일 때

\frac{N}{2}

를, 홀수일 때 3N+1을 출력합니다. 예시로 7 → 22 → 11 → 34 → 17 → 52 → 26 처럼 규칙을 6번 연달아 적용합니다. 이 6단계 과정을 마쳤을 때 결과가 1이 되는 모든 시작값 N을 찾아 그 합을 구하는 문제입니다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 거꾸로 풀기

끝값(1)은 주어졌고 시작값(N)을 찾아야 하니, 정확히 도구 #11(거꾸로 풀기)의 전형적 신호입니다. 기계의 역연산을 정리해 보면, 출력 O의 이전 값은 (1) 항상 짝수 분기로 2O, (2) 홀수 분기로 (O-1)/3 — 단, O-1이 3으로 나누어떨어지고 그 몫이 양의 홀수일 때만 — 두 종류입니다. 매 역단계마다 후보가 갈라질 수 있으므로 도구 #2(빠짐없이 나열하기)로 트리의 가지를 빠짐없이·중복없이 적습니다. 도구 #7(작은 문제로 쪼개기)은 "X의 모든 이전 값 찾기"라는 작은 부분문제를 정의해 매 단계 똑같이 반복할 수 있게 해 줍니다.

1STEP 1

기계의 규칙 거꾸로 하기

기계를 뒤집으면, 출력 O의 이전 값은 2O(항상 유효) 또는 몫이 양의 홀수일 때만 유효한 $\frac{O-1}{3}$ 입니다.

이전값(O) = { 2O } ∪ { (O-1)/3 : 3 ∣ (O-1), (O-1)/3가 양의 홀수 }

"어떤 값이 이 출력을 만들었을까?"라고 묻는 역연산 발상이고, 3으로 나누어떨어지는지 검사하는 부분이 4학년 배수·약수 표준에 정확히 닿습니다.

기계가 출력 O로 바꿀 수 있었던 수는 모두 2O이거나, O-1이 3의 배수이고 그 몫이 홀수일 때에 한하여 (O-1)/3이다.

▸ 왜?

기계의 규칙은 둘뿐이므로, O를 만들어낸 입력 I는 둘 중 하나를 거쳤다: 짝수 규칙 O = I/2는 I = 2O로 되돌아가고, 홀수 규칙 O = 3I+1은 I = (O-1)/3으로 되돌아간다.

▸ 왜?

짝수 규칙은 입력을 반으로 나누므로, 입력을 되찾으려면 반으로 나누기의 반대인 두 배를 하여 I = 2O가 된다.

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

▸ 왜?

홀수 규칙은 3을 곱한 뒤 1을 더하므로, 입력을 되찾으려면 그 과정을 거꾸로 풀어 1을 빼고 3으로 나누어 I = (O-1)/3이 된다.

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

▸ 왜?

두 규칙을 모두 확인하면 빠뜨리는 앞수가 없다. 모든 정수 입력은 짝수 아니면 홀수이고, 이 두 경우가 겹침도 빈틈도 없이 모든 입력을 나누기 때문이다.

짝수와 홀수(패리티)정수는 2로 나누어지면 짝수, 아니면 홀수; 홀×홀은 홀수, 짝×무엇이든 짝수다.

▸ 왜?

두 배한 앞수 2O는 언제나 진짜 짝수 규칙 입력이지만, (O-1)/3은 뺄셈이 3의 배수를 남겨 나눗셈이 홀수인 정수로 딱 떨어질 때에만 유효하다.

▸ 왜?

2O는 O가 든 같은 묶음 두 개로 나뉜 수이고, 같은 두 묶음으로 나뉜다는 것이 곧 수를 짝수로 만드는 것이므로 2O는 짝수 입력이 필요한 짝수 규칙에 항상 들어맞는다.

짝수와 홀수(패리티)정수는 2로 나누어지면 짝수, 아니면 홀수; 홀×홀은 홀수, 짝×무엇이든 짝수다.

▸ 왜?

3으로 나누기는 3 곱하기를 되돌리므로, (O-1)/3은 O-1이 어떤 수의 3배였을 때에만 정수 입력이 되고, 그 입력은 홀수 규칙이 쓰였으려면 홀수여야 한다.

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

4.OA.B.4Work Backwards

2STEP 2

1에서 거꾸로 가기

1의 이전 값은 2 하나뿐 (홀수 분기는 0이라 무효).

이전값(1) = {2}

3STEP 3

2에서 거꾸로 가기

2의 이전 값은 4 하나뿐 (홀수 분기 $\frac{1}{3}$ 은 정수 아님).

이전값(2) = {4}

4STEP 4

4에서 거꾸로 가기

4의 이전 값은 1과 8 — 홀수 분기 $\frac{4-1}{3}$ =1이 살아나 트리가 갈라집니다.

이전값(4) = {1, 8}

5STEP 5

1과 8에서 거꾸로 가기

{1, 8}의 이전 값은 2와 16 (8의 홀수 분기 $\frac{7}{3}$ 은 무효).

이전값({1,8}) = {2, 16}

6STEP 6

2와 16에서 거꾸로 가기

{2, 16}의 이전 값은 4, 5, 32 — 16의 홀수 분기 $\frac{16-1}{3}$ =5가 유효.

이전값({2,16}) = {4, 5, 32}

7STEP 7

마지막으로 거꾸로 가기

마지막 역단계로 시작값 1, 8, 10, 64를 얻습니다 (5와 32의 홀수 분기는 무효).

N ∈ {1, 8, 10, 64}

8STEP 8

네 시작 값 더하기

네 시작값 1 + 8 + 10 + 64를 더하면 83, 선택지 (E).

1 + 8 + 10 + 64 = 83 → (E)

정답

N = 10으로 검산: 10 → 5 → 16 → 8 → 4 → 2 → 1 — 정확히 6단계 만에 1. N = 64로 검산: 64 → 32 → 16 → 8 → 4 → 2 → 1 — 역시 6단계. 나머지 N = 1, 8도 1 → 4 → 2 → 1 사이클을 거쳐 6단계째에 1로 떨어집니다. 유효한 네 값의 합 83이 선택지 (E)와 일치하고, 다른 선택지 중에서 ≡ 2 (mod 3) 인 것은 (E) 하나뿐 — 홀수 분기 한 번이 3의 배수에 1을 더한 형태를 만들기 때문에 직관과도 부합합니다.

💡핵심 정리

이 AMC 8 문제는 사실 4학년 때 배운 곱셈·3으로 나누어떨어지는지 확인하기·덧셈만 알면 풀 수 있어요 — 거기에 "거꾸로 풀기"라는 강력한 전략 하나만 더하면 됩니다!

기계의 규칙 거꾸로 하기
1에서 거꾸로 가기
2에서 거꾸로 가기
4에서 거꾸로 가기
1과 8에서 거꾸로 가기
2와 16에서 거꾸로 가기
마지막으로 거꾸로 가기
네 시작 값 더하기

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

기계의 규칙 거꾸로 하기

1에서 거꾸로 가기

2에서 거꾸로 가기

4에서 거꾸로 가기

1과 8에서 거꾸로 가기

2와 16에서 거꾸로 가기

마지막으로 거꾸로 가기

네 시작 값 더하기

비슷한 유형 더 풀어보기