2024 AMC 10B Problem 19

P16-20~5 minPrint

Coordinate Geometry Number Properties Split into exhaustive cases and handle each Test small/specific values or special cases to find or verify the answer

In the following table, each question mark is to be replaced by "Possible" or "Not Possible" to indicate whether a nonvertical line with the given slope can contain the given number of lattice points (points both of whose coordinates are integers). How many of the 12 entries will be "Possible"?

Show solution without answering

Key insight

A line through two lattice points has a fraction slope. A fraction slope through one lattice point hits infinitely many. So each row has exactly two Possible entries.

Solution

The table has three rows (slope $0$ , a nonzero fraction slope, an irrational slope) and four columns ( $0$ , exactly $1$ , exactly $2$ , more than $2$ lattice points). Two facts settle almost everything.

Fact 1: two lattice points give a fraction slope. If a line passes through $(1, 2)$ and $(4, 7)$ , its slope is $\frac{7 - 2}{4 - 1} = \frac53$ , a fraction. The same happens for any two lattice points, because the slope is one whole number divided by another. So a line with an irrational slope (like $\sqrt2$ ) passes through at most one lattice point.

Fact 2: a fraction slope repeats. Take the line through $(0, 0)$ with slope $\frac23$ . Going $3$ right and $2$ up lands on $(3, 2)$ , then $(6, 4)$ , then $(9, 6)$ , and so on forever. In general, if a line has slope $\frac{p}{q}$ and passes through one lattice point, moving $q$ right and $p$ up lands on another lattice point every time. So such a line has either no lattice points or infinitely many.

Now go row by row.

Slope $0$ (lines $y = c$ ). The line $y = 1.5$ has no lattice points, and $y = 1$ has infinitely many. Exactly $1$ or exactly $2$ is impossible by Fact 2. Possible: $0$ and more than $2$ .
Nonzero fraction slope. The line $y = 2x$ has infinitely many lattice points. The line $y = x + \frac12$ has none: for any whole number $x$ , $y$ ends in $.5$ . Exactly $1$ or $2$ is impossible by Fact 2. Possible: $0$ and more than $2$ .
Irrational slope. The line $y = \sqrt2\,x$ passes through $(0, 0)$ and no other lattice point (by Fact 1). The line $y = \sqrt2\,x + \frac12$ passes through none, since at $x = 0$ it gives $y = \frac12$ and at any other whole $x$ , $y$ is not a whole number. Two or more is impossible by Fact 1. Possible: $0$ and exactly $1$ .

Each row has $2$ "Possible" entries, so there are $3 \cdot 2 = 6$ .

The answer is $\boxed{\textbf{(C)}\ 6}$ .

Why this works

Whether a line's slope is a fraction decides how it meets lattice points. A fraction slope makes the lattice points repeat at a steady step, so there are none or infinitely many. An irrational slope allows at most one. To fill a "possible or not" table, give one example for each "Possible" and a general reason for each "Not Possible".

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The rows are slope $0$ , nonzero rational slope, irrational slope; the columns are $0$ , exactly $1$ , exactly $2$ , more than $2$ lattice points.

Two general facts do most of the work.

If a line contains two lattice points $(a, b)$ and $(c, d)$ , its slope $\frac{d - b}{c - a}$ is rational (or the line is vertical). So an irrational-slope line has at most one lattice point.
If a line with rational slope $\frac{p}{q}$ (lowest terms) contains a lattice point $(a, b)$ , it also contains $(a + q, b + p)$ , $(a + 2q, b + 2p)$ , and so on. So a rational-slope line with one lattice point has infinitely many.

Slope $0$ : $y = c$ . If $c$ is not an integer, there are $0$ lattice points; if $c$ is an integer, infinitely many. Exactly $1$ or $2$ is impossible by fact 2. Possible: $0$ and more than $2$ .

Nonzero rational slope: $y = \frac23 x + \frac12$ has no lattice points (the right side is never an integer for integer $x$ : $\frac{4x + 3}{6}$ has odd numerator); $y = 2x$ has infinitely many. Exactly $1$ or $2$ is impossible by fact 2. Possible: $0$ and more than $2$ .

Irrational slope: $y = \sqrt2\, x$ passes through exactly one lattice point, the origin; $y = \sqrt2\, x + \frac12$ passes through none. Two or more is impossible by fact 1. Possible: $0$ and exactly $1$ .

Each row has $2$ possible entries, for $3 \cdot 2 = 6$ in all.

The answer is $\boxed{\textbf{(C)}\ 6}$ .

Review in the AoPS books

Introduction to Geometry, Chapter 17: Analytic Geometry
Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Introduction to Algebra, Chapter 8: Graphing Lines