In the rectangular grids below, the diagonal touches the interiors of some of the squares in the grid. For example, in the grid, the diagonal intersects the interiors of 6 squares. In the grid, the diagonal crosses through the interiors of 8 squares.
In general, in an 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
Consider the blown up rectangle in the figure below
By visual count, the number of interior crossings equals 8.
The diagonal crosses every horizontal grid line beginning with the -axis. It crosses the interior of four squares namely 1, 2, 3, and 4 corresponding to the 4 rows of the rectangle.
The diagonal also crosses every vertical grid line beginning with the -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 reveals that the -coordinates of these points take on rational values as shown below
Summary for a 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 which are multiples of 3. So an alternative way to find the number of non-lattice points is where 7 is the number of values of .
3. Add the numbers found in step 1 and 2.
Algorithm for a rectangle
1. The diagonal crosses the interior of squares, .
2. Simplify the slope of the diagonal . Find the multiples of starting from . Calculate .
3. Answer = .
Example 1 rectangle
2. because the diagonal crosses all the vertical grid lines at lattice points
Example 2 rectangle
2. Slope = ; among the four values of there are two multiples of 3 namely 0 and 3. Thus,
Example 3 rectangle
2. Slope = ; among the seven values of there are three multiples of 3 namely 0, 3, and 6. Thus,
Answer: Given in Solution.