AMC 10 · 2024 · #10

Grade 6 number-theoryarithmetic

pattern-recognitionmodular-arithmeticrecursive-sequencedivisibility-rules pattern-recognitionsystematic-enumeration ↑ Prerequisites: divisibility-rulesmulti-digit-arithmetic

📏 Short solution 💡 2 insights

Problem

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$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: Start with $n = 100$. Repeat this rule: if $n$ is a multiple of $3$, replace it with $n/3$; otherwise replace it with $n + 10$. What is $n$ after exactly $100$ steps?

Givens: Starting value $n_0 = 100$; Rule: if $3 \mid n$, then $n \to n/3$; if $3 \nmid n$, then $n \to n + 10$; We perform the operation exactly $100$ times; Answer choices: (A) $10$, (B) $20$, (C) $30$, (D) $40$, (E) $50$

Unknowns: The value of $n$ after step $100$

Understand

Restated: Start with $n = 100$. Repeat this rule: if $n$ is a multiple of $3$, replace it with $n/3$; otherwise replace it with $n + 10$. What is $n$ after exactly $100$ steps?

Plan

Primary tool: #5 Look for a Pattern

Secondary: #2 Make an Organized List

A deterministic rule that runs $100$ times on a small pool of positive integers is the classic setup for Tool #5 (Look for a Pattern): once a value repeats, the whole tail of the sequence becomes a cycle, and we never need to do all $100$ steps. The natural way to expose that cycle is Tool #2 (Make an Organized List) — write the first several terms in order and watch for a value to come back. Once the cycle length is known, locating step $100$ inside the cycle is just a remainder calculation.

Execute — Answer: C

#2 Make an Organized List 4.OA.C.5 Step 1

List the first several terms.
Start at $100$, apply the rule each step, and write the result.
Use the divisibility-by-$3$ shortcut: a number is a multiple of $3$ iff its digit sum is.
($100 \to 1$, not divisible; $120 \to 3$, divisible; $60 \to 6$, divisible; etc.)

$$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$$

💡 Generating each next term from the rule is a Grade 4 "follow a given rule to create a number pattern" exercise.

#5 Look for a Pattern 4.OA.C.5 Step 2

Spot the cycle.
The value $20$ shows up after step $6$ and again after step $9$, so between those two appearances the sequence travels $20 \to 30 \to 10 \to 20$.
That is a cycle of length $3$.
From step $6$ onward the sequence is locked into this loop forever.

$$\underbrace{n_0, n_1, \ldots, n_5}_{\text{lead-in}}, \;\; \underbrace{n_6 = 20, \; n_7 = 30, \; n_8 = 10, \; n_9 = 20, \ldots}_{\text{cycle of length } 3}$$

💡 Once any value repeats in a deterministic process, the same chain of successors must repeat too — that is what makes the loop genuine.

#5 Look for a Pattern 6.NS.B.2 Step 3

Locate step $100$ inside the cycle.
The cycle entry is step $6$, so steps $6, 7, 8, 9, \ldots$ trace $20, 30, 10, 20, \ldots$ in lockstep with the cycle positions $0, 1, 2, 0, \ldots$.
The cycle position at step $k$ (for $k \ge 6$) is $(k - 6) \bmod 3$.

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

💡 Dividing the offset $94$ by the cycle length $3$ and keeping the remainder tells you how many "extra" steps remain after completing whole laps — the standard skip-ahead trick for cycles.

#5 Look for a Pattern 4.OA.C.5 Step 4

Read off the answer.
Cycle position $0$ is $20$, position $1$ is $30$, position $2$ is $10$.
Step $100$ sits at position $1$, so $n_{100} = 30$.

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

💡 The remainder is just an index into the three-element cycle list — no further arithmetic needed.

[1] #2 4.OA.C.5 List the first several terms. Start at $100$, apply the rule each step, and writ

[2] #5 4.OA.C.5 Spot the cycle. The value $20$ shows up after step $6$ and again after step $9$,

[3] #5 6.NS.B.2 Locate step $100$ inside the cycle. The cycle entry is step $6$, so steps $6, 7,

[4] #5 4.OA.C.5 Read off the answer. Cycle position $0$ is $20$, position $1$ is $30$, position

Review

Reasonableness: Double-check by counting a few steps forward from $n_6 = 20$ directly. $n_7 = 30$, $n_8 = 10$, $n_9 = 20$ (one full lap of length $3$). So $n_{6 + 3k} = 20$ for every whole number $k$. Take $k = 31$: $6 + 3 \times 31 = 99$, so $n_{99} = 20$. One more step: $20$ is not a multiple of $3$, so $n_{100} = 20 + 10 = 30$. That matches answer (C) and the remainder argument. Also: the cycle values are $\{10, 20, 30\}$, all of which are answer choices, so the answer must be one of (A), (B), (C) — the structure of the choice list is itself a hint.

Alternative: Tool #6 (Guess and Check) directly on landmark steps: from step $6$ the sequence is $20, 30, 10, 20, 30, 10, \ldots$, so $n_k$ equals $20$ when $k \equiv 6 \pmod 3$ (i.e. $k$ is a multiple of $3$), equals $30$ when $k \equiv 1 \pmod 3$, and equals $10$ when $k \equiv 2 \pmod 3$. Since $100 \equiv 1 \pmod 3$, $n_{100} = 30$. Same answer (C) without computing the offset $94$ explicitly.

CCSS standards used (min grade 6)

4.OA.C.5 Generate a number pattern that follows a given rule and identify apparent features of the pattern (Producing the first $9$ terms of the sequence from the rule and observing the repeating loop $20 \to 30 \to 10 \to 20$.)
4.OA.B.4 Find factor pairs and recognize multiples of small whole numbers (Deciding at each step whether the current value is a multiple of $3$ (using the digit-sum test) so we know which branch of the rule to apply.)
6.NS.B.2 Fluently divide multi-digit numbers using the standard algorithm (Computing $94 = 3 \times 31 + 1$ to locate step $100$ inside a cycle of length $3$.)

⭐ Whenever a deterministic rule runs many times, list the first several terms and watch for a repeat — once you find the cycle, a single remainder calculation jumps you straight to step $100$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 6)

More like this