AMC 10 · 2024 · #19

Grade 8 arithmetic

Archetype Lattice / Grid Pattern from Small Cases

slope-interceptcoordinate-geometryratio-proportiongcdlogical-deduction caseworkidentify-subproblemspattern-recognition ↑ Prerequisites: slope-interceptcoordinate-geometryratio-proportion

📏 Medium solution 💡 3 insights 📊 Diagram

Problem

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"?

$\textbf{(A) } 4 \qquad\textbf{(B) } 5 \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 7 \qquad\textbf{(E) } 9$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: Build a $3 \times 4$ table. The rows are slope types: zero slope, nonzero rational slope, irrational slope. The columns are lattice-point counts on a nonvertical line: exactly $0$, exactly $1$, exactly $2$, or two-or-more. Mark each of the $12$ cells "Possible" if some line of that slope type contains exactly that many lattice points, otherwise "Not Possible". How many cells are "Possible"?

Givens: A lattice point is a point $(x, y)$ with both coordinates integers; Lines are nonvertical, so they can be written $y = mx + b$; Row $1$: $m = 0$ (horizontal line); Row $2$: $m = p/q$ with $p, q$ nonzero integers, $\gcd(p,q) = 1$; Row $3$: $m$ is irrational; Column entries: exactly $0$, exactly $1$, exactly $2$, two-or-more lattice points; Answer choices: (A) $4$, (B) $5$, (C) $6$, (D) $7$, (E) $9$

Unknowns: The number of cells (out of $12$) that are "Possible"

Understand

Plan

Primary tool: #4 Use Matrix Logic

Secondary: #7 Identify Subproblems, #1 Draw a Diagram

The problem literally hands you a $3 \times 4$ grid to fill — Tool #4 (Use Matrix Logic) is the structural fit: build the table row by row, derive each cell from a rule, count the ticks. Tool #7 (Identify Subproblems) splits the table into three slope-type rows; each row gets one shared key fact ("$1$ lattice point $\Rightarrow$ infinitely many" for rational slopes; "$\le 1$ lattice point" for irrational slopes), and the four columns are filled from that fact. Tool #1 (Draw a Diagram) gives the proof that rational-slope lines with one lattice point have infinitely many: from $(x_0, y_0)$ take the integer step $(q, p)$ — picture a tilted staircase whose every step is a lattice point.

Execute — Answer: C

#7 Identify Subproblems 8.NS.A.1 Step 1

Key lemma for the irrational row.
If two distinct lattice points $(x_1, y_1), (x_2, y_2)$ sit on a nonvertical line, the slope is $\dfrac{y_2 - y_1}{x_2 - x_1}$, a ratio of integers with $x_2 - x_1 \ne 0$ — hence rational.
Contrapositive: irrational slope $\Rightarrow$ at most one lattice point.

$$m = \dfrac{y_2 - y_1}{x_2 - x_1} \in \mathbb{Q} \;\Rightarrow\; m \;\text{irrational implies} \le 1 \;\text{lattice point}$$

💡 Grade 8 "irrational means not a ratio of integers" — applied to a slope formula, it forbids two lattice points on an irrational-slope line.

#1 Draw a Diagram 8.EE.B.5 Step 2

Key lemma for the rational row.
If a line with rational slope $m = p/q$ ($\gcd(p,q) = 1$) passes through a lattice point $(x_0, y_0)$, then for every integer $k$ the point $(x_0 + kq, \; y_0 + kp)$ also lies on the line and is again a lattice point.
So "one lattice point" forces infinitely many.

$$(x_0 + kq, \; y_0 + kp) \in \text{line} \;\text{for every}\; k \in \mathbb{Z}$$

💡 Picture a tilted staircase rising by $p$ for every horizontal $q$ — once you set one foot on a lattice point, every later step is also a lattice point.

#4 Use Matrix Logic 8.F.A.3 Step 3

Row $1$ — zero slope ($y = b$).
Four cells: exactly $0$ — choose non-integer $b$ (e.g.
$y = 0.5$) — POSSIBLE.
Exactly $1$ — impossible, because $y = b$ with $b$ integer hits every integer $x$, infinitely many lattice points — NOT POSSIBLE.
Exactly $2$ — impossible by the same reason — NOT POSSIBLE.
Two-or-more — choose integer $b$ (e.g.
$y = 3$) — POSSIBLE.
Row $1$ Possible count: $2$.

$$y = b: \;\; (0, \text{No}, \text{No}, \ge 2) = (\checkmark, \times, \times, \checkmark)$$

💡 A horizontal line is the graph of $y = b$ — a Grade 8 linear function with the slope set to zero.

#4 Use Matrix Logic 8.F.A.3 Step 4

Row $2$ — nonzero rational slope.
Cells: exactly $0$ — possible (example $y = \tfrac{1}{2} x + \tfrac{1}{3}$: rewriting as $6y - 3x = 2$ shows no integer solution, since $3 \mid 6y - 3x$ but $3 \nmid 2$) — POSSIBLE.
Exactly $1$ — impossible by the rational-row lemma — NOT POSSIBLE.
Exactly $2$ — impossible by the same lemma — NOT POSSIBLE.
Two-or-more — possible (example $y = \tfrac{2}{3} x$ through $(0,0), (3,2), \dots$) — POSSIBLE.
Row $2$ Possible count: $2$.

$$y = \tfrac{p}{q} x + b: \;\; (0, \text{No}, \text{No}, \ge 2) = (\checkmark, \times, \times, \checkmark)$$

💡 Rational slope acts on lattice points as all-or-infinitely-many — "$1$" and "$2$" can never appear, so only the extreme columns are possible.

#4 Use Matrix Logic 8.NS.A.1 Step 5

Row $3$ — irrational slope.
Cells: exactly $0$ — possible (example $y = \sqrt{2} x + 0.5$: for any integer $x$, $\sqrt{2} x$ is irrational, adding rational $0.5$ stays irrational, never an integer) — POSSIBLE.
Exactly $1$ — possible (example $y = \sqrt{2} x$ through the origin: any other integer $x$ gives an irrational $y$) — POSSIBLE.
Exactly $2$ — forbidden by the irrational lemma — NOT POSSIBLE.
Two-or-more — forbidden by the same lemma — NOT POSSIBLE.
Row $3$ Possible count: $2$.

$$y = (\text{irrat.})x + b: \;\; (0, 1, \text{No}, \text{No}) = (\checkmark, \checkmark, \times, \times)$$

💡 Irrational slope is a hard ceiling at $1$ lattice point — exactly the columns $0$ and $1$ stay open.

#4 Use Matrix Logic 2.OA.B.2 Step 6

Sum the row counts.
Row $1$ contributes $2$ Possible, Row $2$ contributes $2$, Row $3$ contributes $2$.
Total Possible cells $= 2 + 2 + 2 = 6$.

$$\text{Total Possible} = 2 + 2 + 2 = 6 \;\Rightarrow\; \textbf{(C)}$$

💡 Tallying the marks in the filled $3 \times 4$ table is Grade 2 fluent addition.

[1] #7 8.NS.A.1 Key lemma for the irrational row. If two distinct lattice points $(x_1, y_1), (x

[2] #1 8.EE.B.5 Key lemma for the rational row. If a line with rational slope $m = p/q$ ($\gcd(p

[3] #4 8.F.A.3 Row $1$ — zero slope ($y = b$). Four cells: exactly $0$ — choose non-integer $b$

[4] #4 8.F.A.3 Row $2$ — nonzero rational slope. Cells: exactly $0$ — possible (example $y = \t

[5] #4 8.NS.A.1 Row $3$ — irrational slope. Cells: exactly $0$ — possible (example $y = \sqrt{2}

[6] #4 2.OA.B.2 Sum the row counts. Row $1$ contributes $2$ Possible, Row $2$ contributes $2$, R

Review

Reasonableness: The filled grid: \[\begin{array}{l|cccc} & 0 & 1 & 2 & \ge 2 \\ \hline \text{slope } 0 & \checkmark & \times & \times & \checkmark \\ \text{nonzero rat.} & \checkmark & \times & \times & \checkmark \\ \text{irrational} & \checkmark & \checkmark & \times & \times \end{array}\] Six ticks, six "Possible". The two structural rules — "rational slope: $1 \Rightarrow \infty$" and "irrational slope: $\le 1$ ever" — close out the $\times$ cells crisply, and each $\checkmark$ cell has a named witness line. Answer (C) $= 6$ matches.

Alternative: Tool #3 (Eliminate Possibilities). Across the five choices $4, 5, 6, 7, 9$, the irrational row produces exactly $2$ ticks (only columns $0$ and $1$ can have a lattice count). The rational row (zero or nonzero) produces exactly $2$ ticks (columns $1$ and $2$ are both forbidden by the "one $\Rightarrow$ infinitely many" lemma). Three rows times two ticks each is $6$ — only (C) survives. No detailed example construction is required if you trust the two lemmas.

CCSS standards used (min grade 8)

8.NS.A.1 Know that numbers that are not rational are called irrational numbers (Establishing that an irrational slope cannot be written as a ratio of integer differences, so a nonvertical line with irrational slope contains at most one lattice point.)
8.EE.B.5 Graph proportional relationships and interpret the unit rate as slope (Reading slope $p/q$ as "rise $p$ over run $q$" so that from one lattice point the integer step $(q, p)$ produces infinitely many more lattice points on the line.)
8.F.A.3 Interpret the equation y = mx + b as defining a linear function (Writing horizontal lines as $y = b$ and slanted lines as $y = mx + b$ to choose intercepts $b$ that yield $0$, $1$, or infinitely many lattice points per row.)
2.OA.B.2 Fluently add and subtract within 20 using mental strategies (Tallying $2 + 2 + 2 = 6$ Possible cells across the three rows.)

⭐ This AMC 10 problem only needs the Grade 8 rule "slope between two lattice points is rational" — that single fact closes nine of the twelve cells, leaving exactly six "Possible"!

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 8)

More like this