AMC 10 · 2024 · #10

학년 6 number-theoryarithmetic

pattern-recognitionmodular-arithmeticrecursive-sequencedivisibility-rules pattern-recognitionsystematic-enumeration ↑ 선수 지식: divisibility-rulesmulti-digit-arithmetic

📏 짧은 풀이 💡 2 개 인사이트

문제

Consider the following operation. Given a positive integer $n$ , if $n$ is a multiple of $3$ , then you replace $n$ by $\frac{n}{3}$ . If $n$ is not a multiple of $3$ , then you replace $n$ by $n+10$ . Then continue this process. For example, beginning with $n=4$ , this procedure gives $4 \to 14 \to 24 \to 8 \to 18 \to 6 \to 2 \to 12 \to \cdots$ . Suppose you start with $n=100$ . What value results if you perform this operation exactly $100$ times?

$\textbf{(A) }10\qquad\textbf{(B) }20\qquad\textbf{(C) }30\qquad\textbf{(D) }40\qquad\textbf{(E) }50$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $n = 100$ 에서 시작합니다. 다음 규칙을 반복합니다: $n$ 이 $3$ 의 배수이면 $n/3$ 으로 바꾸고, 아니면 $n + 10$ 으로 바꿉니다. 이 연산을 정확히 $100$ 번 수행한 뒤의 $n$ 값을 구하세요.

주어진 것: 시작값 $n_0 = 100$; 규칙: $3 \mid n$ 이면 $n \to n/3$, $3 \nmid n$ 이면 $n \to n + 10$; 연산을 정확히 $100$ 번 수행한다; 선택지: (A) $10$, (B) $20$, (C) $30$, (D) $40$, (E) $50$

구하는 것: $100$ 번째 연산 후 $n$ 의 값

이해

계획

주요 도구: #5 패턴 찾기

보조 도구: #2 정리된 목록 만들기

결정적 규칙을 작은 양의 정수에서 $100$ 번 반복하는 상황은 도구 #5(패턴 찾기)의 전형적 무대입니다. 한 번이라도 값이 다시 나타나면 그 뒤는 통째로 반복 주기가 되어, $100$ 단계를 끝까지 할 필요가 없어집니다. 주기를 드러내는 자연스러운 방법이 도구 #2(정리된 목록 만들기) — 앞쪽 몇 항을 차례대로 적고 어떤 값이 다시 등장하는지 지켜봅니다. 주기 길이만 알면 $100$ 번째 항의 위치는 나머지 계산 한 번으로 끝납니다.

실행 — 정답: C

#2 정리된 목록 만들기 4.OA.C.5 단계 1

앞쪽 항들을 나열합니다.
$100$ 에서 시작해 매 단계마다 규칙을 적용하고 결과를 적습니다.
$3$ 의 배수 판정은 자릿수 합 규칙으로 빠르게 처리합니다 ($100 \to 1$, 배수 아님 / $120 \to 3$, 배수 / $60 \to 6$, 배수 등).

$$100 \xrightarrow{+10} 110 \xrightarrow{+10} 120 \xrightarrow{\div 3} 40 \xrightarrow{+10} 50 \xrightarrow{+10} 60 \xrightarrow{\div 3} 20 \xrightarrow{+10} 30 \xrightarrow{\div 3} 10 \xrightarrow{+10} 20$$

💡 규칙을 따라 다음 항을 만드는 것은 4학년 "주어진 규칙으로 수의 패턴 만들기" 그대로입니다.

#5 패턴 찾기 4.OA.C.5 단계 2

주기를 찾습니다.
값 $20$ 이 $6$ 단계 후와 $9$ 단계 후에 다시 등장하므로, 그 사이 수열은 $20 \to 30 \to 10 \to 20$ 을 돕니다.
길이 $3$ 의 주기입니다.
$6$ 단계 이후부터 수열은 영원히 이 고리에 갇힙니다.

$$\underbrace{n_0, n_1, \ldots, n_5}_{\text{도입부}}, \;\; \underbrace{n_6 = 20, \; n_7 = 30, \; n_8 = 10, \; n_9 = 20, \ldots}_{\text{길이 } 3 \text{ 주기}}$$

💡 결정적 과정에서 어떤 값이 한 번 다시 나오면, 그 뒤를 잇는 수들도 그대로 다시 나옵니다 — 그래서 "고리"가 진짜 고리가 됩니다.

#5 패턴 찾기 6.NS.B.2 단계 3

$100$ 단계를 주기 안에서 위치 짓습니다.
주기 진입점이 $6$ 단계이므로, 단계 $6, 7, 8, 9, \ldots$ 는 주기 위치 $0, 1, 2, 0, \ldots$ 와 정확히 맞춰 $20, 30, 10, 20, \ldots$ 을 줍니다.
$k \ge 6$ 일 때 단계 $k$ 의 주기 위치는 $(k - 6) \bmod 3$.

$$100 - 6 = 94, \;\; 94 = 3 \times 31 + 1 \;\Rightarrow\; 94 \bmod 3 = 1$$

💡 오프셋 $94$ 를 주기 길이 $3$ 으로 나누고 나머지만 남기면, 완전 한 바퀴를 마친 뒤 "몇 칸 더" 가야 하는지가 바로 나옵니다 — 주기 건너뛰기의 표준 수법입니다.

#5 패턴 찾기 4.OA.C.5 단계 4

답을 읽어냅니다.
주기 위치 $0$ 은 $20$, 위치 $1$ 은 $30$, 위치 $2$ 는 $10$.
단계 $100$ 은 위치 $1$ 이므로 $n_{100} = 30$.

$$n_{100} = \text{주기}[1] = 30 \;\Rightarrow\; \textbf{(C)}$$

💡 나머지를 길이 $3$ 짜리 주기 목록의 인덱스로 보면 그뿐, 더 이상의 계산은 없습니다.

[1] #2 4.OA.C.5 앞쪽 항들을 나열합니다. $100$ 에서 시작해 매 단계마다 규칙을 적용하고 결과를 적습니다. $3$ 의 배수 판정은 자릿수 합 규칙으로 빠르게

[2] #5 4.OA.C.5 주기를 찾습니다. 값 $20$ 이 $6$ 단계 후와 $9$ 단계 후에 다시 등장하므로, 그 사이 수열은 $20 \to 30 \to 10 \to

[3] #5 6.NS.B.2 $100$ 단계를 주기 안에서 위치 짓습니다. 주기 진입점이 $6$ 단계이므로, 단계 $6, 7, 8, 9, \ldots$ 는 주기 위치 $0,

[4] #5 4.OA.C.5 답을 읽어냅니다. 주기 위치 $0$ 은 $20$, 위치 $1$ 은 $30$, 위치 $2$ 는 $10$. 단계 $100$ 은 위치 $1$ 이므로

검토

합리성 확인: $n_6 = 20$ 에서 몇 단계 직접 세어 다시 확인합시다. $n_7 = 30$, $n_8 = 10$, $n_9 = 20$ (길이 $3$ 짜리 한 바퀴). 따라서 모든 자연수 $k$ 에 대해 $n_{6 + 3k} = 20$. $k = 31$ 을 넣으면 $6 + 3 \times 31 = 99$ 이므로 $n_{99} = 20$. 한 단계만 더: $20$ 은 $3$ 의 배수가 아니므로 $n_{100} = 20 + 10 = 30$. 답 (C) 와 나머지 논증 모두와 일치합니다. 또한 주기 안의 값이 $\{10, 20, 30\}$ 으로 모두 선택지에 들어 있다는 점도 답이 (A), (B), (C) 중 하나라는 힌트가 됩니다.

대안 접근: 도구 #6(추측하고 확인하기)으로 핵심 단계만 직접 봅니다. $6$ 단계부터 수열은 $20, 30, 10, 20, 30, 10, \ldots$ 이므로 $k \equiv 6 \pmod 3$ ($k$ 가 $3$ 의 배수)일 때 $n_k = 20$, $k \equiv 1 \pmod 3$ 일 때 $n_k = 30$, $k \equiv 2 \pmod 3$ 일 때 $n_k = 10$. $100 \equiv 1 \pmod 3$ 이므로 $n_{100} = 30$. 오프셋 $94$ 를 명시적으로 계산하지 않고도 같은 답 (C).

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

4.OA.C.5 주어진 규칙을 따라 수 패턴을 만들고 그 특징을 파악 (규칙으로 수열의 처음 $9$ 항을 만들어 $20 \to 30 \to 10 \to 20$ 의 반복 고리를 발견하는 데 사용.)
4.OA.B.4 약수쌍 찾기와 작은 수의 배수 인식 (각 단계마다 현재 값이 $3$ 의 배수인지 판정해 (자릿수 합 규칙) 어떤 가지를 적용할지 정하는 데 사용.)
6.NS.B.2 표준 알고리즘으로 여러 자리 수의 나눗셈을 능숙히 수행 ($94 = 3 \times 31 + 1$ 을 계산해 $100$ 단계가 길이 $3$ 주기의 어디에 있는지 위치 짓는 데 사용.)

⭐ 결정적 규칙을 여러 번 돌릴 때는 앞쪽 몇 항을 나열해 반복이 일어나는지 살펴보세요 — 주기를 찾고 나면 나머지 계산 한 번으로 $100$ 번째 단계까지 단숨에 건너뜁니다.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

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

비슷한 유형 더 풀어보기