Diagonal Cut II (8 x 12)

We have a rectangular grid consisting of 8 x 12 small squares. If a diagonal is drawn from one corner to the opposite corner, how many squares does the diagonal go through?

Answer

From diagonal cut I, we know that if $\gcd(m,n) = 1$ , the answer is $$m + n - 1$$ . Now $\gcd(8,12) = 4$ . We can break up the grid into 4 smaller rectangles (they do not make up the whole grid), each of size $2 \times 3$ . Since $\gcd(2,3) = 1$ , each smaller rectangle’s diagonal passes through $$2 + 3 - 1 = 4$$ squares, giving a total of $4 \times 4 = 16$ .

The reason why we divide the grid in such a way is due to the following. The slope of the diagonal (bottom-left to top-right) is $\tfrac{8}{12} = \tfrac{2}{3}$ . The diagonal intersects interior lattice points at $$(2,3)$$ , $$(4,6)$$ , and $$(6,9)$$ . Hence, we only study the 4 sub-rectangles of size $2 \times 3$ .