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

Let S be the 30 × 30 grid of lattice points {(x, y) : 1 ≤ x ≤ 30, 1 ≤ y ≤ 30, x, y ∈ Z} (so |S| = 900). For exactly 300 points of S to lie on or below the line y = m x (i.e., y ≤ m x), the slope m must lie in an interval of length

\frac{a}{b}

in lowest terms. Find a + b.

Pick an answer.

(A)

~31

(B)

~47

(C)

~62

(D)

~72

(E)

~85

AMC 10 2021 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

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 ∼ $\frac{1}{3}$ of the bounding square) to guess m ≈ $\frac{2}{3}$ , then verify exactly. Tool #5 (Pattern) — group the 30 terms of the sum Σ_x = 1³⁰ ⌊ $\frac{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 = $\frac{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

Each column x holds min(⌊mx⌋, 30) points with y ≤ mx, so N(m) = Σ min(⌊mx⌋, 30); for m ≤ 1 the 30-cap never bites.

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

2STEP 2

By area, the cut triangle is $\frac{1}{3}$ of the 900-square: $\frac{450m}{900}$ = $\frac{1}{3}$ gives m ≈ $\frac{2}{3}$ , and 30·( $\frac{2}{3}$ ) = 20 ≤ 30 stays safe.

m ≈

\frac{2}{3}

3STEP 3

Group x by residue mod 3: each triple sums to 6k − 3, and Σ (6k − 3) over k = 1..10 gives N( $\frac{2}{3}$ ) = 300. ✓

\frac{2}{3}

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

4STEP 4

Just below $\frac{2}{3}$ , the 10 on-line points (3, 2), …, (30, 20) each drop out, so N falls 300 → 290 — hence m_lo = $\frac{2}{3}$ is included.

m_lo =

\frac{2}{3}

(inclusive)

5STEP 5

N jumps up at the next $\frac{k}{x}$ above $\frac{2}{3}$ ; minimizing $\frac{k}{x}$ − $\frac{2}{3}$ = $\frac{3k − 2x}{3x}$ needs numerator 3k − 2x = 1 with x as large as possible.

min

\frac{k}{x}

\frac{2}{3}

\frac{1}{3x}

; maximize x with 3k - 2x = 1

6STEP 6

Solving 3k − 2x = 1 gives x = 1 + 3t, k = 1 + 2t; the largest x ≤ 30 is t = 9 → x = 28, so m_hi = $\frac{19}{28}$ and m ∈ [ $\frac{2}{3}$ , $\frac{19}{28}$ ).

m_hi =

\frac{19}{28}

; m ∈ [

\frac{2}{3}

\frac{19}{28}

)

7STEP 7

Interval length: $\frac{19}{28}$ − $\frac{2}{3}$ = $\frac{57 − 56}{84}$ = $\frac{1}{84}$ , already lowest terms, so a + b = 1 + 84 = 85, choice (E).

\frac{19}{28}

\frac{2}{3}

\frac{1}{84}

; a + b = 1 + 84 = 85 → (E)

Answer

~85

Sanity.

\frac{2}{3}

≈ 0.6667 and

\frac{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

\frac{k}{x}

moves only one lattice point above-or-below — so the average gap between jumps is roughly

\frac{1}{30² / something}

. The value

\frac{1}{84}

is in the right ballpark (much less than 1, more than

\frac{1}{900}

). Alternative check: at m =

\frac{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 10 problem only needs Grade 7-8 estimation and number theory you already know — area $\frac{1}{3}$ of the square → guess m ≈ $\frac{2}{3}$ ; verifying by groups of three confirms exactly 300 lattice points; the next jump up happens at the smallest $\frac{k}{x}$ ＞ $\frac{2}{3}$ with x ≤ 30, which comes from 3k - 2x = 1 with largest x = 28, giving $\frac{19}{28}$ ; interval length is $\frac{19}{28}$ - $\frac{2}{3}$ = $\frac{1}{84}$ , so a + b = 1 + 84 = 85.

More like this