AMC 10 · 2019 · #10

Grade 6 geometry-2d

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Grid Diagonal Cell Count

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

📏 Short solution 💡 2 insights

Problem

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?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

Counting tiles along a diagonal of a 10 × 17 grid is hard to do directly — Tool #9: shrink to small grids (1 × 1, 2 × 3, 3 × 4, 2 × 5, 3 × 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).

1STEP 1

Try the easy case: a 2 × 3 grid's diagonal cuts one vertical and one horizontal line, so it visits 4 tiles.

2 × 3 grid: tiles visited = 4

2STEP 2

More cases: 3 × 4 gives 6 tiles and 3 × 5 gives 7 tiles — the diagonal never hits a lattice point since gcd = 1.

3 × 4: tiles = 6; 3 × 5: tiles = 7

3STEP 3

The pattern: start in 1 tile, then each internal line crossed adds one, giving a + b - 1 when gcd(a, b) = 1.

Tiles visited = a + b - 1 when gcd(a, b) = 1

4STEP 4

Check the formula: 2 + 3 - 1 = 4 and 3 + 5 - 1 = 7 both match the diagrams.

2 + 3 - 1 = 4 ✓, 3 + 5 - 1 = 7 ✓

5STEP 5

Confirm gcd(10, 17) = 1: 17 is prime and doesn't divide 10, so the shortcut applies.

gcd(10, 17) = 1

6STEP 6

Plug a = 10, b = 17 into a + b - 1: the bug visits 26 tiles.

10 + 17 - 1 = 26

7STEP 7

So 26 tiles matches choice (C).

26 → (C)

Answer

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

💡Key takeaway

This AMC 10 problem only needs Grade 6 pattern-spotting you already know — try small grids first. A 2 × 3 diagonal crosses 4 tiles, a 3 × 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.

More like this