AMC 10 · 2019 · #10

Grade 6 geometry-2d

Archetype Lattice / Grid Pattern from Small Cases

gcdlattice-pathspattern-recognitioncoordinate-geometry pattern-recognitionidentify-subproblems ↑ Prerequisites: gcd

📏 Short solution 💡 2 insights

Problem

A rectangular floor that is $10$ feet wide and $17$ feet long is tiled with $170$ one-foot square tiles. A bug walks from one corner to the opposite corner in a straight line. Including the first and the last tile, how many tiles does the bug visit?

$\textbf{(A) } 17 \qquad\textbf{(B) } 25 \qquad\textbf{(C) } 26 \qquad\textbf{(D) } 27 \qquad\textbf{(E) } 28$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: A floor that is $10$ feet wide and $17$ feet long is tiled with $170$ one-foot square tiles. A bug walks in a straight line from one corner to the diagonally opposite corner. Counting both the starting tile and the ending tile, how many tiles does the bug pass through?

Givens: Floor dimensions: $10 \times 17$ (in feet); Tiles are $1 \times 1$ squares, so there is a $10 \times 17$ grid of tile cells; Bug walks in a straight diagonal from one corner to the opposite corner; Choices: (A) $17$, (B) $25$, (C) $26$, (D) $27$, (E) $28$

Unknowns: Total number of tiles the straight diagonal touches

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #1 Draw a Diagram, #5 Look for a Pattern, #7 Identify Subproblems, #3 Eliminate Possibilities

Counting tiles along a diagonal of a $10 \times 17$ grid is hard to do directly — Tool #9: shrink to small grids ($1 \times 1$, $2 \times 3$, $3 \times 4$, $2 \times 5$, $3 \times 5$) and count by drawing (Tool #1). Tool #5 spots the formula $a + b - \gcd(a, b)$. Then plug in $a = 10$, $b = 17$ and match the choice (Tool #3).

Execute — Answer: C

#1 Draw a Diagram 5.G.A.2 Step 1

Solve the easier version first.
Draw a $2 \times 3$ grid and the diagonal.
The diagonal crosses one internal vertical line and one internal horizontal line, splitting into $4$ tile-segments.
Tiles visited $= 4$.

$$2 \times 3 \text{ grid: tiles visited} = 4$$

💡 Draw the diagonal and count which tiles it cuts through.

#9 Solve an Easier Related Problem 5.G.A.2 Step 2

More small cases.
$3 \times 4$: the diagonal crosses $2$ internal vertical lines and $3$ internal horizontal lines, never passing through a lattice point (since $\gcd(3, 4) = 1$).
Total tiles $= 6$.
$3 \times 5$: crosses $2$ vertical and $4$ horizontal internal lines, $\gcd = 1$, tiles $= 7$.

$$3 \times 4: \text{tiles} = 6; \quad 3 \times 5: \text{tiles} = 7$$

💡 Each internal line the diagonal crosses adds $1$ new tile.

#5 Look for a Pattern 4.OA.C.5 Step 3

Spot the pattern.
In an $a \times b$ grid with $\gcd(a, b) = 1$: the bug starts in $1$ tile, then every time the diagonal crosses an internal vertical line ($a - 1$ of them) or internal horizontal line ($b - 1$ of them), it enters one new tile.
Total $= 1 + (a - 1) + (b - 1) = a + b - 1$.

$$\text{Tiles visited} = a + b - 1 \quad \text{when } \gcd(a, b) = 1$$

💡 Start with $1$ tile, then add $1$ for each grid line you cross.

#5 Look for a Pattern 4.OA.A.3 Step 4

Verify on $2 \times 3$: $a + b - 1 = 2 + 3 - 1 = 4$.
✓.
And $3 \times 5$: $3 + 5 - 1 = 7$.
✓.
Both match the diagram counts.

$$2 + 3 - 1 = 4 \quad\checkmark, \quad 3 + 5 - 1 = 7 \quad\checkmark$$

💡 Pattern checks out on two independent small cases.

#3 Eliminate Possibilities 6.NS.B.4 Step 5

Confirm $\gcd(10, 17) = 1$.
$17$ is prime and does not divide $10$, so they share no factor besides $1$.
The shortcut formula applies.

$$\gcd(10, 17) = 1$$

💡 $17$ is prime — quick gcd check.

#7 Identify Subproblems 4.OA.A.3 Step 6

Apply the formula to $a = 10, b = 17$: tiles $= 10 + 17 - 1 = 26$.

$$10 + 17 - 1 = 26$$

💡 Plug $10$ and $17$ into the small-case formula.

#3 Eliminate Possibilities 4.NBT.A.2 Step 7

Tiles $= 26$ matches choice (C).

$$26 \Rightarrow \textbf{(C)}$$

💡 Read off the matching choice.

[1] #1 5.G.A.2 Solve the easier version first. Draw a $2 \times 3$ grid and the diagonal. The d

[2] #9 5.G.A.2 More small cases. $3 \times 4$: the diagonal crosses $2$ internal vertical lines

[3] #5 4.OA.C.5 Spot the pattern. In an $a \times b$ grid with $\gcd(a, b) = 1$: the bug starts

[4] #5 4.OA.A.3 Verify on $2 \times 3$: $a + b - 1 = 2 + 3 - 1 = 4$. ✓. And $3 \times 5$: $3 + 5

[5] #3 6.NS.B.4 Confirm $\gcd(10, 17) = 1$. $17$ is prime and does not divide $10$, so they shar

[6] #7 4.OA.A.3 Apply the formula to $a = 10, b = 17$: tiles $= 10 + 17 - 1 = 26$.

[7] #3 4.NBT.A.2 Tiles $= 26$ matches choice (C).

Review

Reasonableness: Sanity check: the bug must cross $9$ internal vertical lines (between the $10$ columns) and $16$ internal horizontal lines (between the $17$ rows). Since $\gcd(10, 17) = 1$, the diagonal never passes through any lattice point in the interior — so no crossing is shared. Each of these $9 + 16 = 25$ crossings moves the bug into a new tile, on top of the $1$ starting tile, giving $1 + 25 = 26$ tiles. The general formula for $\gcd(a, b) = 1$ is $a + b - 1$. For coprime sides, this is between $\max(a, b)$ and $a + b - 1$, so $26$ is sensible — close to the $a + b = 27$ upper bound and well above $\max = 17$. ✓

Alternative: Tool #1 (Draw a Diagram) with a careful sketch on grid paper: split the $10 \times 17$ floor into a $5 \times 17$ half on top and $5 \times 17$ on the bottom — but $\gcd(5, 17) = 1$ so the half-diagonals each visit $5 + 17 - 1 = 21$ tiles? That double-counts the center line — better: just count once on the full diagonal using the formula $a + b - \gcd(a, b)$ which is the standard generalization. Same answer $26$.

CCSS standards used (min grade 6)

5.G.A.2 Represent real-world and mathematical problems by graphing points (Drawing the small $2 \times 3$, $3 \times 4$, $3 \times 5$ grids and tracing the diagonal to count tiles.)
4.OA.C.5 Generate a number or shape pattern following a given rule (Generalizing the small-case counts into the formula $a + b - 1$ for $\gcd(a, b) = 1$.)
4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (Verifying the formula on $2 \times 3$ and $3 \times 5$, and plugging $a = 10, b = 17$ to compute $10 + 17 - 1 = 26$.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Confirming $\gcd(10, 17) = 1$ so the simple formula applies (no shared lattice points along the diagonal).)
4.NBT.A.2 Read and write multi-digit whole numbers and compare using symbols (Matching $26$ to choice (C).)

⭐ This AMC 10 problem only needs Grade 6 pattern-spotting you already know — try small grids first. A $2 \times 3$ diagonal crosses $4$ tiles, a $3 \times 5$ diagonal crosses $7$. The formula is $a + b - 1$ when $\gcd(a, b) = 1$. Since $\gcd(10, 17) = 1$, the bug visits $10 + 17 - 1 = 26$ tiles.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 6)

More like this