Problem 23 · 2024 AMC 8
Hard
Number Theory
factorizationgridgrid-counting
Show answer
Answer: C — 7000 cells.
Show hints
Hint 1 of 2
Think about WHEN the segment moves into a new cell: every time it crosses a vertical or horizontal gridline. So count crossings — but watch the special moment when it crosses both at once (through a grid corner) and gets two for the price of one.
Still stuck? Show hint 2 →
Hint 2 of 2
Technique (lattice cell-crossing formula): cells = (horizontal offset) + (vertical offset) − gcd(those offsets). The gcd counts the corner-crossings you'd otherwise double-count. Apply it to offsets 3000 and 5000.
Show solution
Approach: use the lattice-line cell-count formula
- A line segment whose horizontal offset is a and vertical offset is b crosses a + b − gcd(a, b) grid cells. (You'd cross a + b cells if the line never hit a grid corner; each lattice-point crossing collapses two cell-entries into one, saving 1 per shared factor.)
- From (2000, 3000) to (5000, 8000): horizontal offset 3000, vertical offset 5000.
- gcd(3000, 5000) = 1000. Cells = 3000 + 5000 − 1000 = 7000.
Another way — scale down (MAA):
- The slope from (2000, 3000) to (5000, 8000) is 5/3. The segment is equivalent to 1000 copies of a primitive (0,0)→(3,5) piece, since gcd(3000, 5000) = 1000.
- Each primitive (3,5) segment crosses 7 cells. Total: 7 × 1000 = 7000.
Mark:
· log in to save