2021 AMC 10B Problem 25

For $0 < m \le 1$, the points of $S$ on or below $y = mx$ in column $x$ are $(x, 1), \dots, (x, \lfloor mx \rfloor)$, so the count is $N(m) = \sum_{x=1}^{30} \lfloor mx \rfloor$. This is roughly the area $\frac12 \cdot 30 \cdot 30m = 450m$, and $450m = 300$ suggests $m = \frac23$.

Check $m = \frac23$. Group $x$ into triples $3k+1, 3k+2, 3k+3$ for $k = 0, \dots, 9$: the floors are $2k, 2k+1, 2k+2$, summing to $6k + 3$. Total $\sum_{k=0}^{9}(6k+3) = 6 \cdot 45 + 30 = 300$. Exactly right.

Lower end. The ten points $(3, 2), (6, 4), \dots, (30, 20)$ lie on the line and are counted. Any $m < \frac23$ loses them, so $\frac23$ is the left endpoint (included).

Upper end. As $m$ grows, $N(m)$ stays $300$ until the line reaches another point of $S$, i.e. until $m$ equals the smallest fraction $\frac{y}{x} > \frac23$ with $x, y \le 30$. Since $\frac yx - \frac23 = \frac{3y - 2x}{3x}$, the best candidates have $3y - 2x = 1$ with $x$ as large as possible: $x \equiv 1 \pmod 3$, so $x = 28$, $y = 19$, giving a gap of $\frac{1}{84}$. Any fraction with $3y - 2x \ge 2$ has gap at least $\frac{2}{90} > \frac{1}{84}$. So the interval is $\left[\frac23, \frac{19}{28}\right)$.

Its length is $\frac{19}{28} - \frac23 = \frac{57 - 56}{84} = \frac{1}{84}$, so $a + b = 85$.

The answer is $\boxed{\textbf{(E)}\ 85}$.

The count of lattice points under a line is a step function of the slope: it changes only when the line sweeps through a lattice point. So the set of good slopes is an interval between two consecutive "lattice slopes." Estimation (area $\approx 450m$) finds the interval quickly, and the endpoints come from the number-theoretic question of which fraction with bounded denominator is nearest to $\frac23$ from above.

• Taking an interval symmetric around 2/3, or forgetting that points on the line count, so 2/3 itself is the lower endpoint and 19/28 the upper.
• Picking the next-larger fraction with small denominator, such as $\frac{7}{10}$ or $\frac{5}{7}$, instead of searching denominators up to $30$.