AMC 10 · 2021 · #25

Grade 8 number-theory

Archetype Lattice / Grid Pattern from Small Cases

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 set of lattice points in the coordinate plane, both of whose coordinates are integers between $1$ and $30,$ inclusive. Exactly $300$ points in $S$ lie on or below a line with equation $y=mx.$ The possible values of $m$ lie in an interval of length $\frac ab,$ where $a$ and $b$ are relatively prime positive integers. What is $a+b?$

Pick an answer.

(A)

~31

(B)

~47

(C)

~62

(D)

~72

(E)

~85

View mode:

Toolkit + CCSS Solution

Understand

Restated: Let $S$ be the $30 \times 30$ grid of lattice points $\{(x, y) : 1 \le x \le 30,\; 1 \le y \le 30,\; x, y \in \mathbb{Z}\}$ (so $|S| = 900$). For exactly $300$ points of $S$ to lie on or below the line $y = m x$ (i.e., $y \le m x$), the slope $m$ must lie in an interval of length $\tfrac{a}{b}$ in lowest terms. Find $a + b$.

Givens: $S = $ lattice points $(x, y)$ with $1 \le x, y \le 30$ — total $900$; Line $y = m x$ passes through origin; Exactly $300$ lattice points of $S$ satisfy $y \le m x$; Possible $m$ form an interval of length $\tfrac{a}{b}$ in lowest terms; Answer choices: (A) $31$, (B) $47$, (C) $62$, (D) $72$, (E) $85$

Unknowns: $a + b$

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #1 Draw a Diagram, #7 Identify Subproblems, #3 Eliminate Possibilities

Tool #9 (Easier Problem) — first use a continuous-area estimate (the line cuts a triangle of area $\sim \tfrac{1}{3}$ of the bounding square) to guess $m \approx \tfrac{2}{3}$, then verify exactly. Tool #5 (Pattern) — group the $30$ terms of the sum $\sum_{x = 1}^{30} \lfloor \tfrac{2x}{3} \rfloor$ by $x \bmod 3$ to see a clean arithmetic-series formula. Tool #1 (Diagram) — sketch the $30 \times 30$ grid with the line $y = \tfrac{2}{3} x$ passing exactly through $(3, 2), (6, 4), \ldots, (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.

Execute — Answer: E

#7 Identify Subproblems 8.F.A.1 Step 1

Translate "count of lattice points on or below the line" into a sum.
For each $x \in \{1, 2, \ldots, 30\}$, the column $\{(x, 1), (x, 2), \ldots, (x, 30)\}$ contributes the number of $y \in \{1, \ldots, 30\}$ with $y \le mx$, which equals $\min(\lfloor m x \rfloor, 30)$.
So $N(m) = \sum_{x = 1}^{30} \min(\lfloor m x \rfloor, 30)$.
For modest $m$ (so that $30 m \le 30$, i.e.
$m \le 1$), the $\min$ never bites and $N(m) = \sum_{x = 1}^{30} \lfloor m x \rfloor$.

$$N(m) = \sum_{x = 1}^{30} \min(\lfloor m x \rfloor, 30)$$

💡 Per column, count how many lattice $y$'s stay below the line — that's a floor of $mx$, capped at $30$.

#9 Solve an Easier Related Problem 7.G.B.6 Step 2

Estimate $m$ by area (Tool #9).
The line $y = m x$ cuts off a triangle of area $\tfrac{1}{2} \cdot 30 \cdot (30 m) = 450 m$ from the $30 \times 30$ continuous square of area $900$ (for $m \le 1$).
$300$ lattice points $\approx \tfrac{1}{3}$ of $900$, so $\tfrac{450 m}{900} = \tfrac{1}{3} \Rightarrow m \approx \tfrac{2}{3}$.
At $m = \tfrac{2}{3}$, $30 m = 20 \le 30$, so the $\min$ in $N$ never activates — we're in the safe range.

$$m \approx \tfrac{2}{3}$$

💡 Continuous area gives a sharp guess; we'll verify the exact count is $300$ next.

#5 Look for a Pattern 8.F.B.4 Step 3

Verify $N(\tfrac{2}{3}) = 300$ exactly by grouping $x = 1, 2, \ldots, 30$ in triples (Tool #5).
Write $x = 3k - 2, 3k - 1, 3k$ for $k = 1, \ldots, 10$.
Then $\lfloor \tfrac{2}{3}(3k - 2) \rfloor = \lfloor 2k - \tfrac{4}{3} \rfloor = 2k - 2$ (since $\tfrac{4}{3} > 1$); $\lfloor \tfrac{2}{3}(3k - 1) \rfloor = \lfloor 2k - \tfrac{2}{3} \rfloor = 2k - 1$; $\lfloor \tfrac{2}{3}(3k) \rfloor = 2k$.
Triple sum: $(2k - 2) + (2k - 1) + 2k = 6k - 3$.
Total: $\sum_{k = 1}^{10} (6k - 3) = 6 \cdot \tfrac{10 \cdot 11}{2} - 30 = 330 - 30 = 300$.
✓

$$N(\tfrac{2}{3}) = \sum_{k = 1}^{10}(6k - 3) = 300$$

💡 Group by $x \bmod 3$ — each residue class gives an arithmetic-progression-of-floors pattern.

#1 Draw a Diagram 8.F.A.1 Step 4

Find the lower endpoint $m_{\text{lo}}$ of the interval.
For $m$ slightly less than $\tfrac{2}{3}$, say $m = \tfrac{2}{3} - \varepsilon$, at the multiples $x = 3k$ we get $m x = 2k - 3 k \varepsilon < 2k$, so $\lfloor m x \rfloor$ drops from $2k$ to $2k - 1$ for each of the $10$ values $k = 1, \ldots, 10$.
Total count drops by exactly $10$, from $300$ to $290$.
So $m = \tfrac{2}{3}$ is the SMALLEST slope yielding $N = 300$; the interval starts at $m_{\text{lo}} = \tfrac{2}{3}$ (inclusive).
The line $y = \tfrac{2}{3} x$ passes through the lattice points $(3, 2), (6, 4), \ldots, (30, 20)$ — which are included in the "on or below" count.

$$m_{\text{lo}} = \tfrac{2}{3} \;\text{(inclusive)}$$

💡 The count jumps DOWN by $10$ as soon as the line drops just below the diagonal points $(3, 2), (6, 4), \ldots$

#7 Identify Subproblems 7.NS.A.3 Step 5

Find the upper endpoint $m_{\text{hi}}$.
$N(m)$ jumps UP by some amount each time $m$ crosses a value of the form $\tfrac{k}{x}$ for $1 \le x \le 30$ and $k$ a positive integer (because $\lfloor m x \rfloor$ then ticks up by $1$).
The next jump above $\tfrac{2}{3}$ comes at the smallest rational $\tfrac{k}{x}$ with $\tfrac{k}{x} > \tfrac{2}{3}$ and $1 \le x \le 30$.
Equivalently, minimize $\tfrac{k}{x} - \tfrac{2}{3} = \tfrac{3k - 2x}{3x}$ over positive integers $k$ and $1 \le x \le 30$ with $3k - 2x > 0$.
Since the numerator is a positive integer, it's at least $1$; the smallest positive value is exactly $3k - 2x = 1$, giving difference $\tfrac{1}{3x}$.
To minimize $\tfrac{1}{3x}$ we maximize $x$.

$$\min \tfrac{k}{x} - \tfrac{2}{3} = \tfrac{1}{3x};\;\text{maximize } x \text{ with } 3k - 2x = 1$$

💡 Smallest fraction just above $\tfrac{2}{3}$ comes from the largest allowed denominator that satisfies the Diophantine condition.

#7 Identify Subproblems 7.NS.A.3 Step 6

Solve the Diophantine $3k - 2x = 1$ with $1 \le x \le 30$.
General solution: $(k, x) = (1 + 2t, 1 + 3t)$ for integer $t \ge 0$.
$x \le 30 \Rightarrow 1 + 3t \le 30 \Rightarrow t \le 9$.
Largest $t = 9$ gives $x = 28$, $k = 19$, so $\tfrac{k}{x} = \tfrac{19}{28}$.
Check: $3 \cdot 19 - 2 \cdot 28 = 57 - 56 = 1$ ✓.
So $m_{\text{hi}} = \tfrac{19}{28}$ (exclusive: as soon as $m$ reaches $\tfrac{19}{28}$, $\lfloor m \cdot 28 \rfloor$ ticks from $18$ to $19$, so $N$ jumps to $301$).
The interval of valid $m$ is $[\tfrac{2}{3}, \tfrac{19}{28})$.

$$m_{\text{hi}} = \tfrac{19}{28};\quad m \in [\tfrac{2}{3}, \tfrac{19}{28})$$

💡 $t = 9$ pushes $x$ all the way to $28$ — the largest $x \le 30$ in the family.

#3 Eliminate Possibilities 5.NF.A.1 Step 7

Length of interval: $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{19 \cdot 3 - 2 \cdot 28}{28 \cdot 3} = \tfrac{57 - 56}{84} = \tfrac{1}{84}$.
Since $\gcd(1, 84) = 1$, this is already in lowest terms with $a = 1, b = 84$.
So $a + b = 1 + 84 = 85$, matching choice (E).

$$\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84};\;\; a + b = 1 + 84 = 85 \Rightarrow \textbf{(E)}$$

💡 Common-denominator subtraction yields a beautifully clean $\tfrac{1}{84}$ — and $85$ is on the list.

[1] #7 8.F.A.1 Translate "count of lattice points on or below the line" into a sum. For each $x

[2] #9 7.G.B.6 Estimate $m$ by area (Tool #9). The line $y = m x$ cuts off a triangle of area $

[3] #5 8.F.B.4 Verify $N(\tfrac{2}{3}) = 300$ exactly by grouping $x = 1, 2, \ldots, 30$ in tri

[4] #1 8.F.A.1 Find the lower endpoint $m_{\text{lo}}$ of the interval. For $m$ slightly less t

[5] #7 7.NS.A.3 Find the upper endpoint $m_{\text{hi}}$. $N(m)$ jumps UP by some amount each tim

[6] #7 7.NS.A.3 Solve the Diophantine $3k - 2x = 1$ with $1 \le x \le 30$. General solution: $(k

[7] #3 5.NF.A.1 Length of interval: $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{19 \cdot 3 - 2 \cdot

Review

Reasonableness: Sanity. $\tfrac{2}{3} \approx 0.6667$ and $\tfrac{19}{28} \approx 0.6786$, so the interval has length $\approx 0.012$. With $30$ values of $x$ and $30$ values of $y$, each step of $\Delta m$ across a value $\tfrac{k}{x}$ moves only one lattice point above-or-below — so the average gap between jumps is roughly $\tfrac{1}{30^2 / \text{something}}$. The value $\tfrac{1}{84}$ is in the right ballpark (much less than $1$, more than $\tfrac{1}{900}$). Alternative check: at $m = \tfrac{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), \ldots, (30, 20)$ are already on the line) and open on the right.

Alternative: Tool #5 (Pattern) + Tool #14 (Finite differences) without the Diophantine machinery: enumerate all $\tfrac{k}{x}$ slightly above $\tfrac{2}{3}$ for each $x = 1, 2, \ldots, 30$. For each $x$, the smallest $k$ with $\tfrac{k}{x} > \tfrac{2}{3}$ is $k = \lceil \tfrac{2x}{3} \rceil + (\tfrac{2x}{3} \in \mathbb{Z}\;? \;1 : 0)$. Tabulate $\tfrac{k}{x}$ and find the minimum above $\tfrac{2}{3}$. The minimum occurs at $x = 28$ with $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84}$; nearby candidates like $\tfrac{17}{25} = \tfrac{2}{3} + \tfrac{1}{75}$ and $\tfrac{13}{19} = \tfrac{2}{3} + \tfrac{1}{57}$ are LARGER, so do not give the upper bound.

CCSS standards used (min grade 8)

5.NF.A.1 Add and subtract fractions with unlike denominators (Computing $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84}$ via common denominator $84$.)
7.G.B.6 Solve real-world problems involving area, surface area, and volume (Initial estimate $m \approx \tfrac{2}{3}$ from the triangle-area / square-area ratio $= \tfrac{1}{3}$.)
7.NS.A.3 Solve real-world problems involving the four operations with rational numbers (Solving the Diophantine $3k - 2x = 1$ with $1 \le x \le 30$, picking the largest valid $x$ to minimize $\tfrac{1}{3x}$.)
8.F.A.1 Understand that a function is a rule that assigns exactly one output to each input (Treating $N(m) = \sum_{x = 1}^{30} \lfloor m x \rfloor$ as a (step) function of $m$, jumping up at each $\tfrac{k}{x}$.)
8.F.B.4 Construct a function to model a linear relationship between two quantities (Grouping the $30$ summands by $x \bmod 3$ to express $N(\tfrac{2}{3}) = \sum_{k = 1}^{10}(6k - 3)$ as an arithmetic-series-of-residues formula.)

⭐ This hardest AMC 10 problem only needs Grade 7-8 estimation and number theory you already know — area $\tfrac{1}{3}$ of the square $\to$ guess $m \approx \tfrac{2}{3}$; verifying by groups of three confirms exactly $300$ lattice points; the next jump up happens at the smallest $\tfrac{k}{x} > \tfrac{2}{3}$ with $x \le 30$, which comes from $3k - 2x = 1$ with largest $x = 28$, giving $\tfrac{19}{28}$; interval length is $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84}$, so $a + b = 1 + 84 = 85$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: E

Review

CCSS standards used (min grade 8)

More like this