2011 AMC 10B Problem 24

Step A: when does the line hit a lattice point?

1. For a whole number $x$ from $1$ to $100$, the line goes through $(x, mx + 2)$. This is a lattice point exactly when $mx + 2$ is a whole number, which means $mx$ is a whole number.
2. Example: if $m = \frac{3}{5}$, then at $x = 5$ we get $mx = 3$, and the line passes through $(5, 5)$.
3. In general, $mx = k$ (a whole number) means $m = \frac{k}{x}$. So the line hits a lattice point in the range exactly when $m$ can be written as a fraction with bottom number $100$ or less.

Step B: turn it into a fraction question.

1. So we need every slope between $\frac12$ and $a$ to avoid all such fractions. The largest $a$ is the first such fraction above $\frac12$: the smallest fraction bigger than $\frac12$ with bottom at most $100$.

Step C: find the fraction closest to $\frac12$ from above.

1. How far is $\frac{k}{x}$ above $\frac12$? Write $\frac{k}{x} - \frac{1}{2} = \frac{2k - x}{2x}$. The top, $2k - x$, is a whole number at least $1$.
2. To make the gap small, we want the top as small as possible ($2k - x = 1$) and the bottom as large as possible.
3. $2k - x = 1$ means $x = 2k - 1$ is odd. The largest odd $x$ up to $100$ is $99$, with $k = 50$. That gives $\frac{50}{99}$, which is $\frac{1}{198}$ above $\frac12$.
4. Could $x = 100$ do better? Then $2k - 100$ is even, so it is at least $2$. The best is $\frac{51}{100}$, which is $\frac{2}{200} = \frac{1}{100}$ above $\frac12$. That is farther than $\frac{1}{198}$.
5. So $\frac{50}{99}$ is the smallest fraction above $\frac12$ with bottom at most $100$.

Step D: check both halves.

1. Every $m$ between $\frac12$ and $\frac{50}{99}$ is safe, because there is no allowed fraction in between.
2. If $a$ were bigger than $\frac{50}{99}$, the slope $m = \frac{50}{99}$ would be included, and that line passes through $(99, 50 + 2) = (99, 52)$. So $a$ cannot be bigger.

The answer is $\boxed{\textbf{(B)}\ \frac{50}{99}}$.

A lattice-point question about a line with slope $m$ is really a question about which fractions $m$ can equal. The gap formula $\frac{2k - x}{2x}$ shows that the fraction just above $\frac12$ has top and bottom as close to "half" as possible, with the largest odd bottom number.

Use the answer choices. Choice (C) $\frac{51}{100}$ and (E) $\frac{13}{25}$ are both bigger than $\frac{50}{99}$ (for example $51 \times 99 = 5049 > 50 \times 100 = 5000$), so they would include the slope $\frac{50}{99}$, which hits $(99, 52)$. Choice (D) $\frac{52}{101}$ is bigger still. Choice (A) $\frac{51}{101}$ is smaller than $\frac{50}{99}$, since $51 \times 99 = 5049 < 50 \times 101 = 5050$; it is safe but not the largest. That leaves (B).

At an integer $x$, the point $(x, mx + 2)$ is a lattice point exactly when $mx$ is an integer, i.e. when $m = \frac{k}{x}$ for some integer $k$. So the line avoids lattice points for $0 < x \le 100$ precisely when $m$ is not a fraction with denominator (before or after reduction) at most $100$.

Therefore the interval $\left(\frac12, a\right)$ is safe as long as it contains no fraction $\frac{k}{x}$ with $1 \le x \le 100$, and the largest possible $a$ is the smallest such fraction exceeding $\frac12$.

For $\frac{k}{x} > \frac12$ we need $2k - x \ge 1$, so
$$\frac{k}{x} - \frac12 = \frac{2k - x}{2x} \ge \frac{1}{2x}.$$
To make this gap as small as possible we want $2k - x = 1$ (so $x$ must be odd) and $x$ as large as possible: $x = 99$, $k = 50$. The candidate is $\frac{50}{99}$, with gap $\frac{1}{198}$.

Could an even denominator do better? With $x = 100$ the best is $2k - x = 2$, giving $\frac{51}{100}$ and gap $\frac{1}{100}$, which is larger. Cross-check: $50 \cdot 100 = 5000 < 51 \cdot 99 = 5049$, so indeed $\frac{50}{99} < \frac{51}{100}$.

Hence every $m$ in $\left(\frac12, \frac{50}{99}\right)$ is safe, while $m = \frac{50}{99}$ itself hits the lattice point $(99, 52)$. The maximum $a$ is $\frac{50}{99}$.

The answer is $\boxed{\textbf{(B)}\ \frac{50}{99}}$.