How many squares does a diagonal cross?

Question

Take a rectangle divided into a 15 by 36 grid of unit squares (15 rows, 36 columns). Draw the straight diagonal line from one corner to the opposite corner. How many of the little unit squares does the diagonal pass through the interior of?

Accepted Answer

The diagonal passes through 48 unit squares. The formula. For a diagonal of an m 	imes n grid, the number of unit squares it passes through is m + n - \gcd(m, n), where \gcd is the greatest common divisor. Here m = 15, n = 36, and \gcd(15, 36) = 3, so: 15 + 36 - 3 = \mathbf{48}. Why the formula works. As the diagonal travels from corner to corner, it enters a new square every time it crosses a grid line. There are m - 1 horizontal interior grid lines and n - 1 vertical ones, and each crossing bumps the square-count by one. Starting in the first square, that gives 1 + (m-1) + (n-1) = m + n - …

How many squares does a diagonal cross?

Your answer

More Brainteasers questions