Competition · AMC preparation · step 4 of 4

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

Shift to the differences

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

Count cells for small cases

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

Look for a pattern in the table

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

See why the count drops

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

Count the lattice points on the way

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)

Recognizing the "largest common divisor" of two numbers as the count of lattice steps is exactly the Grade 6 GCD standard.

A segment drawn from (0,0) to (Δ x, Δ y) passes through the interiors of exactly Δ x + Δ y - gcd(Δ x, Δ y) grid cells.

▸ Why?

If it threaded no interior corner the segment would meet Δ x + Δ y - 1 cells: it starts inside one cell and slips into one new cell at every grid line it steps over.

▸ Why?

Climbing from (0,0) to (Δ x, Δ y), the segment's x-value passes each whole number 1 up to Δ x - 1 exactly once and its y-value each whole number 1 up to Δ y - 1 exactly once, so it steps over exactly (Δ x - 1) + (Δ y - 1) grid lines.

One-to-one correspondenceIf each thing here pairs with exactly one thing there, the two groups are the same size.

▸ Why?

The cells it meets are the one starting cell together with one fresh cell per grid line crossed, with none skipped and none counted twice, so the total is simply those parts added up.

Whole is the sum of its partsBreak a thing into pieces with no gaps or overlaps and the pieces add back to the whole.

▸ Why?

Every interior corner the segment threads trims one off that base count, because at a corner a vertical and a horizontal grid line meet, so its two crossings land on a single point and open only one new cell instead of two.

▸ Why?

Two crossings landing on the very same point mark just one move into a new cell, since each new cell a segment enters matches one distinct crossing point, and a shared corner is a single point.

One-to-one correspondenceIf each thing here pairs with exactly one thing there, the two groups are the same size.

▸ Why?

The segment threads exactly gcd(Δ x, Δ y) - 1 interior corners, so removing them from Δ x + Δ y - 1 leaves Δ x + Δ y - gcd(Δ x, Δ y); its whole-number points sit evenly spaced along the step (Δ x / g, Δ y / g) with g = gcd(Δ x, Δ y).

▸ Why?

Both legs split into g equal parts — Δ x is g groups of Δ x / g and Δ y is g groups of Δ y / g — so the identical step (Δ x / g, Δ y / g) taken g times walks from start to end, resting on g - 1 corners strictly in between.

Multiplication as equal groupsa times b means a equal groups of b — it is just repeated adding of the same amount.

▸ Why?

No further corner hides between those evenly spaced points, because g is the greatest number dividing both Δ x and Δ y, so the step (Δ x / g, Δ y / g) cannot be shrunk to a smaller whole-number step.

Multiplication as equal groupsa times b means a equal groups of b — it is just repeated adding of the same amount.

6.NS.B.4Look For A Pattern

6STEP 6

Apply the formula to the big numbers

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!

Shift to the differences
Count cells for small cases
Look for a pattern in the table
See why the count drops
Count the lattice points on the way
Apply the formula to the big numbers

A parent dashboard for the family lives at sensimlab.com.

Shift to the differences

Count cells for small cases

Look for a pattern in the table

See why the count drops

Count the lattice points on the way

Apply the formula to the big numbers

More like this