AMC 8 · 2024 · #23

Grade 6 rate-ratio

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Grid Diagonal Cell Count

gcdcoordinate-geometrypattern-recognition pattern-recognition ↑ Prerequisites: gcdcoordinate-geometrymulti-digit-arithmetic

📏 Long solution 💡 4 insights 📊 Diagram

Problem

On a giant sheet of graph paper, one straight line segment runs from (2000, 3000) to (5000, 8000). We want the total number of grid cells whose interior the segment crosses (cells the segment only grazes at a corner do not count). For warm-up we are told that the segment (0,4)→(2,0) colors exactly 4 cells, shown in the figure.

Pick an answer.

(A)

6000

(B)

6500

(C)

7000

(D)

7500

(E)

8000

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

How to solve

Strategy Solve an Easier Related Problem

The numbers 2000, 3000, 5000, 8000 are far too big to count cells one by one, so the natural first move is Tool #9 — shrink the problem to small endpoints (0,0)→(Δ x, Δ y), then use Tool #1 to actually draw each tiny segment on graph paper and collect the cell counts in a small table. Tool #5 (Look for a Pattern) then turns the table into a rule of the form "cells = Δ x + Δ y - (correction)", and the correction turns out to depend on how many lattice points the segment passes through. Finally we apply the rule to the original Δ x, Δ y. This stays in the elementary toolkit — no need for Tool #13 (Algebra) or a memorized formula.

1STEP 1

Slide the whole picture left 2000 and down 3000 so the segment becomes (0,0)→(3000, 5000); the cell count is unchanged.

Δ x = 5000 - 2000 = 3000, Δ y = 8000 - 3000 = 5000

2STEP 2

Draw tiny segments from (0,0) and count: (1,1):1, (1,2):2, (2,3):4, (2,4):4, (3,5):7 cells.

(1,1):1, (1,2):2, (2,3):4, (2,4):4, (3,5):7

3STEP 3

Guess cells = Δx + Δy - 1: fits (1,2),(2,3),(3,5) but (2,4) gives 5 not 4 and (2,2) gives 3 not 2 — the guess overshoots.

(2,4):2+4-1=5 ≠ 4, (2,2):2+2-1=3 ≠ 2

4STEP 4

Where the segment hits an interior lattice point like (1,2) it crosses both grid lines at once, so subtract one more: cells = Δx + Δy - g.

(2,4):segment hits (1,2) → 2+4-2=4 ✓

5STEP 5

The lattice points on the segment number gcd(Δx, Δy), so g is exactly that gcd: N = Δx + Δy - gcd(Δx, Δy), matching every small case.

N = Δ x + Δ y - gcd(Δ x, Δ y)

6STEP 6

gcd(3000, 5000) = 1000 since both are 1000 times coprime 3 and 5, so N = 3000 + 5000 - 1000 = 7000 — choice (C).

N = 3000 + 5000 - 1000 = 7000 → (C)

Answer

7000

Apply the formula N = Δ x + Δ y - gcd to the warm-up picture: (0,4)→(2,0) has Δ x = 2, Δ y = 4, gcd(2,4)=2, giving 2+4-2 = 4, which matches the 4 colored cells in the figure. By size, the answer should sit between Δ x + Δ y - gcd_max = 7000 and Δ x + Δ y - 1 = 7999 at the very most, so 7000 is reasonable. Choices (A) 6000 would over-correct and (E) 8000 = Δ x + Δ y would skip the lattice-point correction entirely — both are the classic traps.

💡Key takeaway

This AMC 8 problem only needs Grade 6 greatest common factor (GCD) you already know!

More like this