AMC 10 · 2021 · #25

Grade 8 number-theory

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Lattice Constraint Analysis

floor-functionlinear-diophantinecoordinate-geometryfraction-arithmetic easier-related-problempattern-recognitionbound-inequality-then-enumerate ↑ Prerequisites: floor-functioncoordinate-geometry

📏 Long solution 💡 4 insights

Problem

There are nine hundred lattice points forming a thirty by thirty grid. For exactly three hundred of them to lie on or below a line through the origin, its slope must lie in some interval. Write that interval's length in lowest terms and add the numerator and denominator.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem) — first use a continuous-area estimate (the line cuts a triangle of area ∼ 1/3 of the bounding square) to guess m ≈ 2/3, then verify exactly. Tool #5 (Pattern) — group the 30 terms of the sum Σ_x = 1³⁰ ⌊ 2x/3 ⌋ by x mod 3 to see a clean arithmetic-series formula. Tool #1 (Diagram) — sketch the 30 × 30 grid with the line y = 2/3 x passing exactly through (3, 2), (6, 4), …, (30, 20). Tool #7 (Subproblems) — find the lower bound and the upper bound of the interval separately. Tool #3 (Eliminate) — confirm a + b matches a choice.

1STEP 1

Write the count as a formula

Write it as a sum over columns.

N(m) = Σ_x = 1³⁰ min(⌊ m x ⌋, 30)

2STEP 2

Estimate the slope

Estimate a candidate slope.

m ≈ 2/3

3STEP 3

Check the candidate

Counting confirms it exactly.

N(2/3) = Σ_k = 1¹⁰(6k - 3) = 300

4STEP 4

Fix the lower end

That value is the lower end.

m_lo = 2/3 (inclusive)

5STEP 5

Find the next lattice point

Find the lattice point caught first.

min k/x - 2/3 = 1/3x; maximize x with 3k - 2x = 1

6STEP 6

Fix the upper end

That slope is the upper end.

m_hi = 19/28; m ∈ [2/3, 19/28)

7STEP 7

Take the length and add

Adding gives 85.

19/28 - 2/3 = 1/84; a + b = 1 + 84 = 85 → (E)

Answer

Sanity. 2/3 ≈ 0.6667 and 19/28 ≈ 0.6786, so the interval has length ≈ 0.012. With 30 values of x and 30 values of y, each step of Δ m across a value k/x moves only one lattice point above-or-below — so the average gap between jumps is roughly 1/(30² / something). The value 1/84 is in the right ballpark (much less than 1, more than 1/900). Alternative check: at m = 19/28 a single lattice point (28, 19) enters the "on or below" count, taking N from 300 to 301 — consistent with the interval being closed on the left (where (3, 2), …, (30, 20) are already on the line) and open on the right.

💡Key takeaway

This hardest AMC 12 problem only needs Grade 7-8 estimation and number theory you already know — area 1/3 of the square → guess m ≈ 2/3; verifying by groups of three confirms exactly 300 lattice points; the next jump up happens at the smallest k/x ＞ 2/3 with x ≤ 30, which comes from 3k - 2x = 1 with largest x = 28, giving 19/28; interval length is 19/28 - 2/3 = 1/84, so a + b = 1 + 84 = 85.