Competition · AMC preparation · step 4 of 4

AMC 10 · 2019A · #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)
17
(B)
25
(C)
26
(D)
27
(E)
28

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 a smaller grid

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

Test more small cases

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

Spot the pattern

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

Verify on the small grids

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

Check the gcd of 10 and 17

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

gcd(10, 17) = 1
6STEP 6

Apply the formula

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

10 + 17 - 1 = 26
7STEP 7

Match 26 to the choices

So 26 tiles matches choice (C).

26 → (C)
Answer
26
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.

  • Try a smaller grid
  • Test more small cases
  • Spot the pattern
  • Verify on the small grids
  • Check the gcd of 10 and 17
  • Apply the formula
  • Match 26 to the choices

A parent dashboard for the family lives at sensimlab.com.

More like this

Same problem type. Tags show what each one shares with this problem.