AMC 8 · 2024 · #23

• First make the numbers manageable.
• Slide the whole picture — segment **and** grid lines together — **left by $2000$ and down by $3000$**.
• The segment $(2000,3000)\to(5000,8000)$ becomes $(0,0)\to(3000, 5000)$, but every grid line moves the same amount, so the number of colored cells is unchanged.
• So we only need to count cells crossed by a segment from $(0,0)$ to $(\Delta x, \Delta y) = (3000, 5000)$.

💡 Computing $5000-2000$ and $8000-3000$ is exactly Grade 4 fluent multi-digit subtraction.

• Now use Tool #9: pick very small $(\Delta x, \Delta y)$ pairs and **draw each segment on graph paper** to count cells.
• $(0,0)\to(1,1)$ is the diagonal of one square and only grazes corners of two others, so it colors $1$ cell.
• $(0,0)\to(1,2)$: $2$ cells.
• $(0,0)\to(2,3)$: $4$ cells.
• $(0,0)\to(2,4)$ has the same shape as the warm-up $(0,4)\to(2,0)$, so $4$ cells.
• $(0,0)\to(3,5)$: $7$ cells.

💡 Plotting points and a segment on the coordinate plane and counting cells underneath is exactly the Grade 5 coordinate-plane standard.

• Use Tool #5 on the table.
• A first guess "cells $= \Delta x + \Delta y$" fails right away on $(1,2)$ giving $3$ instead of $2$.
• Try "$\Delta x + \Delta y - 1$": $(1,2):1+2-1=2$ ✓, $(2,3):2+3-1=4$ ✓, $(3,5):3+5-1=7$ ✓, $(1,1):1+1-1=1$ ✓.
• But $(2,4)$ gives $2+4-1=5$, off by $1$ from the actual $4$.
• And $(0,0)\to(2,2)$ has $2$ cells but the guess gives $3$, again off by $1$.
• So the formula needs to subtract one *extra* for those special cases.

💡 Tabulating cases, proposing a rule, and noticing exactly where it breaks is the Grade 4 "generate a pattern following a rule" activity.

• Look at the pictures of $(2,4)$ and $(2,2)$ to see *why* they need an extra $-1$.
• The segment $(0,0)\to(2,4)$ passes through the lattice point $(1,2)$ in the middle; the segment $(0,0)\to(2,2)$ passes through $(1,1)$.
• At each such interior lattice point the segment crosses a vertical grid line and a horizontal grid line **at the same point**, so it gains one fewer new cell than usual.
• That gives the corrected rule: cells $= \Delta x + \Delta y - g$, where $g$ counts how many "corner crossings" we made (and equals the number of lattice points on the segment, endpoints adjusted).

💡 Reading the coordinates of interior lattice points on a plotted segment is exactly Grade 5 coordinate-plane work.

• How many lattice points sit on the segment $(0,0)\to(\Delta x, \Delta y)$?
• They have the form $(k\Delta x/d,\; k\Delta y/d)$ for $k = 0, 1, \ldots, d$, where $d$ is the largest number that divides both $\Delta x$ and $\Delta y$.
• Check the table: for $(2,4)$, $d=2$ (three lattice points: $(0,0),(1,2),(2,4)$); for $(3,5)$, $d=1$ (only endpoints); for $(2,2)$, $d=2$.
• That $d$ is the **greatest common divisor** of $\Delta x$ and $\Delta y$.
• So the formula is $$N = \Delta x + \Delta y - \gcd(\Delta x, \Delta y),$$ and every small example in our table checks out.

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

• Apply the formula to the big numbers.
• We need $\gcd(3000, 5000)$.
• Since $3000 = 1000 \times 3$ and $5000 = 1000 \times 5$, and $3$ and $5$ are different primes (no common factor beyond $1$), the largest common divisor is $1000$: $\gcd(3000,5000)=1000$.
• Plug in: $N = 3000 + 5000 - 1000 = 7000$.
• So Rodrigo colors $\mathbf{7000}$ cells, matching choice (C).

💡 Finding $\gcd(3000,5000)=1000$ by factoring out the common $1000$ is a direct Grade 6 GCD computation.