AMC 10 · 2015 · #20

Grade 8 patternnumber-theory

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Periodic Placement Formula

recursive-sequencefunction-compositionmodular-arithmeticperiodic-function pattern-recognitioneasier-related-problem ↑ Prerequisites: recursive-sequencemodular-arithmetic

📏 Long solution 💡 4 insights

Problem

Each row of a table is built by looking up the previous row at positions it names itself. Find one far-out entry.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Look for a Pattern

The index 2015 is a bluff: nothing can be computed at that height directly, so the real target is the row-to-row machine and the shape it settles into. Tool #15 (Organize Information in More Ways) comes first, because the definition has to be reorganised before it can be trusted — the clause f(i,j) = f(i-1,f(i,j-1)) looks circular, and the first job is to show it is not, and that row i depends on nothing but row i-1. Tool #4 (Introduce a Variable) then names each row as a function R_i on {0,1,2,3,4}; in that language the whole rule collapses to one sentence — row i is the first five stops of the trip that starts at 1 and keeps applying R_i-1. Tool #5 (Look for a Pattern) drives the computation of rows 0 through 5 and, more importantly, exposes why the rows degrade: the trip through 1 keeps getting shorter until it stops moving at all. Tool #9 (Solve an Easier Related Problem) closes the gap, replacing row 2015 by the far easier claim that one particular entry, f(i,1), never changes again.

1STEP 1

Check the rule is not circular

The rule is well founded, not circular.

f(i,0) → f(i-1,1) and f(i,j) → f(i,j-1), f(i-1,·): each call strictly decreases (i,j) in lexicographic order

2STEP 2

Read each row as a function

Each row reads as one repeated function.

R_i(j) = R_i-1^ j+1(1), so row i = (R_i-1(1), R_i-1²(1), R_i-1³(1), R_i-1⁴(1), R_i-1⁵(1))

3STEP 3

Rows 0, 1, 2 stay rearrangements

The first rows are still rearrangements.

R₀(x) = mod₅(x+1), row 1 = (2,3,4,0,1); R₁(x) = mod₅(x+2), row 2 = (3,0,2,4,1); R₂(x) = mod₅(2x+3)

4STEP 4

Row 3 is where it breaks

One row later that breaks.

x ≡ 2x+3 (mod 5) → x ≡ 2; walk 1 → 0 → 3 → 4 → 1 has period 4, so row 3 = (0,3,4,1,0)

5STEP 5

The walk shortens to a standstill

The walk shortens until it stands still.

R₃: 1 → 3 → 1 (period 2), so row 4 = (3,1,3,1,3); then R₄(1) = 1, so row 5 = (1,1,1,1,1)

6STEP 6

One frozen entry locks every later row

One frozen entry locks every later row.

R_i(1) = 1 → R_i+1(j) = R_i^ j+1(1) = 1 for all j → R_i+1(1) = 1; base f(4,1) = 1, so f(i,j) = 1 for all i ≥ 5

7STEP 7

Land on row 2015

So the far entry is 1, choice (B).

2015 ≥ 5 → f(2015,2) = 1 → (B)

Answer

Rebuild rows 5 and 6 straight from the three original clauses, ignoring the row-map shortcut, to be sure the shortcut did not smuggle anything in. f(5,0) = f(4,1) = 1; f(5,1) = f(4, f(5,0)) = f(4,1) = 1, and the same substitution gives f(5,2) = f(5,3) = f(5,4) = 1. Then f(6,0) = f(5,1) = 1 and f(6,j) = f(5, f(6,j-1)) = f(5,1) = 1. Both rows come out all ones, matching. A second check on direction: the set of values appearing in row i runs {0,1,2,3,4}, {0,1,2,3,4}, {0,1,2,3,4}, {0,1,3,4}, {1,3}, {1} for i = 0,1,2,3,4,5 — it only ever shrinks, so the collapse cannot reverse itself at some later row. The answer 1, choice (B), is the one survivor; the other four options are values that had already dropped out by row 5 (2 vanished at row 3, 0 and 4 at row 4, 3 at row 5).

💡Key takeaway

When a rule keeps feeding its own output back in, hunt for the input that maps to itself: once the process lands on a fixed point it can never leave, so row 2015 takes no more work than row 5.

Check the rule is not circular
Read each row as a function
Rows 0, 1, 2 stay rearrangements
Row 3 is where it breaks
The walk shortens to a standstill
One frozen entry locks every later row
Land on row 2015