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