AMC 10 Step by Step
Log inSign up
Printable

2019 AMC 10A Problem 10

Problem onlyBack to the problem
2019 AMC 10A Problem 10AMC 10 Step by Step
Name:                             Date: September 13, 2026
Paths & Grids · difficulty 2 of 5 · about 3 min · position P1-10

A rectangular floor that is 1010 feet wide and 1717 feet long is tiled with 170170 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?

  1. A)

    1717

  2. B)

    2525

  3. C)

    2626

  4. D)

    2727

  5. E)

    2828

Answer

C

Key insight

Each time the diagonal crosses a grid line it enters a new tile; it crosses 16 vertical and 9 horizontal lines, never at a corner since gcd(10,17) = 1.

Solution

The bug starts in a corner tile. Every time its path crosses one of the interior grid lines it leaves one tile and enters a new one, so
tiles visited=1+(number of grid-line crossings),\text{tiles visited} = 1 + (\text{number of grid-line crossings}),
provided the path never passes through a corner where a vertical and a horizontal line meet (which would count one crossing for two lines).

Between the two 1010-foot walls there are 17−1=1617 - 1 = 16 interior vertical lines, and between the 1717-foot walls there are 10−1=910 - 1 = 9 interior horizontal lines. The diagonal passes through a lattice corner only at points (17t,10t)(17t, 10t) with both coordinates integers; since gcd⁡(10,17)=1\gcd(10, 17) = 1 that happens only at the two ends. So the 16+9=2516 + 9 = 25 crossings are all distinct.

Tiles visited: 1+25=261 + 25 = 26.

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

Why this works

A diagonal of an m×nm \times n grid meets m+n−gcd⁡(m,n)m + n - \gcd(m,n) cells: m−1m - 1 horizontal crossings plus n−1n - 1 vertical crossings plus the first tile, minus the gcd⁡(m,n)−1\gcd(m,n) - 1 interior corners where two crossings coincide. Whenever the sides are coprime there are no such corners and the count is simply m+n−1m + n - 1.

The trap

Answering 10 + 17 = 27 by forgetting that the starting tile is counted once, or forgetting the gcd correction in the general formula.

Common mistakes

  • Answering 10 + 17 = 27 by forgetting that the starting tile is counted once, or forgetting the gcd correction in the general formula.
  • Thinking the bug visits only one tile per column (1717) or per row, as if the path moved in steps rather than continuously.

Techniques

Map the objects to something easier to count · Set up the equation/formula and compute; no special trick needed