## Interior Crossings

In the rectangular grids below, the diagonal touches the interiors of some of the squares in the grid. For example, in the $5\times 2$ grid, the diagonal intersects the interiors of 6 squares. In the $4\times 6$ grid, the diagonal crosses through the interiors of 8 squares.

In general, in an $n\times m$ rectangular grid of squares, a diagonal would pass through the interiors of how many squares in the grid?
Source: NCTM Problem to Ponder March 2011

SOLUTION
Consider the blown up $4\times 6$ rectangle in the figure below

Observation 1
By visual count, the number of interior crossings equals 8.
Observation 2
The diagonal crosses every horizontal grid line beginning with the $x$-axis. It crosses the interior of four squares namely 1, 2, 3, and 4 corresponding to the 4 rows of the rectangle.
Observation 2
The diagonal also crosses every vertical grid line beginning with the $y$-axis. It crosses the interior of four squares namely 5, 6, 7, and 8. At these squares the diagonal crosses the vertical lines at non-lattice points.
It is easy to find these non-lattice points in a non-visual way. A table of values for the diagonal’s equation  $y=\frac{4}{6}x=\frac{2}{3}x$ reveals that the $y$-coordinates of these points take on rational values as shown below

 x y 0 0 1 2/3 2 4/3 3 3 4 8/3 5 10/3 6 4

Summary for a $4\times 6$ rectangle
1. The diagonal crosses the interior of 4 squares corresponding to the 4 rows of the rectangle
2. The diagonal crosses the interior of 4 more squares corresponding to the 4 non-lattice points of intersection of the diagonal and the vertical grid lines. Notice the lattice points occur at $x=0,3,6$ which are multiples of 3. So an alternative way to find the number of non-lattice points is $7-3=4$ where 7 is the number of values of $x=0,1,2,3,4,5,6$.
3. Add the numbers found in step 1 and 2.

Algorithm for a $n\times m$ rectangle
1. The diagonal crosses the interior of $n$ squares, $A=n$.
2. Simplify the slope of the diagonal $\frac{n}{m}=\frac{a}{b}$. Find the multiples of $b$ starting from $0,1,2,3,\cdots,m$. Calculate $B=m+1-\left (number\; of\; multiples\right )$.
3. Answer = $A+B$.

Example 1 $5\times 5$ rectangle
1. $A=5$
2. $B=0$ because the diagonal crosses all the vertical grid lines at lattice points
3. $A+B=5+0=5$

Example 2 $5\times 3$ rectangle
1. $A=5$
2. Slope = $\frac{5}{3}$; among the four values of $x=0,1,2,3$ there are two multiples of 3 namely 0 and 3. Thus, $B=4-2=2$
3. $A+B=5+2=7$.

Example 3 $10\times 6$ rectangle
1. $A=10$
2. Slope = $\frac{10}{6}=\frac{5}{3}$; among the seven values of $x=0,1,2,3,4,5,6$ there are three multiples of 3 namely 0, 3, and 6. Thus, $B=7-3=4$
3. $A+B=10+4=14$.