2021 AMC 10B Problem 25

Step 1: count points column by column.

1. The slope must be less than $1$ here (with slope $1$ the line already has $465$ points on or below it). For such a slope $m$, in column $x$ the points on or below the line are $(x, 1), (x, 2), \ldots$ up to height $mx$. So column $x$ holds $mx$ rounded down points.
2. The total is roughly the area of the triangle under the line from $x = 0$ to $x = 30$: $\frac12 \times 30 \times 30m = 450m$. Setting $450m = 300$ suggests $m = \frac23$.

Step 2: check $m = \frac23$ exactly.

1. Look at the first few columns: $x = 1, 2, 3$ give heights $\frac23, \frac43, 2$, which round down to $0, 1, 2$. That is $3$ points.
2. The next three columns $x = 4, 5, 6$ give $2, 3, 4$ points: $9$ in total. Each group of three columns has $6$ more points than the group before it.
3. The ten groups hold $3, 9, 15, \ldots, 57$ points. Their sum is $\frac{(3 + 57) \times 10}{2} = 300$. Exactly right, so $m = \frac23$ works.

Step 3: the left end of the interval.

1. The line $y = \frac23 x$ passes exactly through $10$ points of $S$: $(3, 2), (6, 4), \ldots, (30, 20)$. They count, because "on" the line is allowed.
2. Lowering the slope even a tiny bit drops those $10$ points below $300$. So $\frac23$ is the smallest slope that works.

Step 4: the right end of the interval.

1. As the slope grows from $\frac23$, the count stays at $300$ until the line hits a new point of $S$. So we need the point $(x, y)$ whose slope $\frac{y}{x}$ is just above $\frac23$, with $x, y$ between $1$ and $30$.
2. Compare $\frac{y}{x}$ with $\frac23$ using a common denominator: $\frac{y}{x} - \frac23 = \frac{3y - 2x}{3x}$. To make this small, make the top as small as possible (namely $1$) and the bottom as large as possible.
3. $3y - 2x = 1$ has solutions $(x, y) = (1, 1), (4, 3), (7, 5), \ldots$, with $x$ going up by $3$ each time. The largest $x$ up to $30$ is $x = 28$, $y = 19$. The gap is $\frac{1}{3 \cdot 28} = \frac{1}{84}$.
4. Any point with $3y - 2x = 2$ or more has a gap of at least $\frac{2}{3 \cdot 30} = \frac{1}{45}$, which is bigger. So $(28, 19)$ is the next point the line reaches, at slope $\frac{19}{28}$. At that slope the count becomes $301$, so $\frac{19}{28}$ itself does not work.

Step 5: the length.

12. The slopes that work run from $\frac23$ up to (but not including) $\frac{19}{28}$. The length is
$$\frac{19}{28} - \frac23 = \frac{57 - 56}{84} = \frac{1}{84}.$$
13. So $a + b = 1 + 84 = 85$.

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

The number of points under a line changes only when the line sweeps across a point. So the good slopes form an interval between two "point slopes." An area estimate finds the right neighborhood fast, and then the question becomes which fraction with a small bottom number sits closest above $\frac23$.

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}$.