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 x 2 grid, the diagonal intersects the interiors of 6 squares. In the 4 x 6 grid, the diagonal crosses through the interiors of 8 squares.

In general, in an n x m rectangular grid of squares, a diagonal would pass through the interiors of how many squares in the grid?

Some Ponderings:  

Recall that the March Problem to Ponder asked about the number of squares whose interiors are crossed by a diagonal in a rectangular grid. We noted that in a 5 x 2 grid the diagonal crosses the interiors of 6 squares, in a 4 x 6 grid the diagonal crosses the interiors of 8 squares, and the challenge was to predict how many squares will be crossed in general, in an n x m rectangular grid of squares.

Of course, one could count the number of squares that a diagonal crosses by hand, but that wouldn’t be mathematics—it would be torture—especially for larger grids.

One strategy that students often start with on this problem is to make lists and look for any patterns that might show up. This can lead to some “notices and wonders.” For example, consider the following:

We notice that the pattern seems to be that each time we add a column or row to the grid, we increase the number of squares crossed by 1. But then when we look at the next grid, a 5 x 5 grid, that pattern breaks down, and we wonder, what’s going on?  

“Oh well, maybe squares are just a special case,” our students might think. Not exactly. Consider the collection below:

And if you check, you’ll see that the diagonal crosses 10 squares in a 4 x 7 grid, and 8 squares in a 4 x 8 grid! So, clearly, more is going on here than just increasing by 1 square crossed when we add an additional row or column to the grid, with a special case for square grids thrown in.

The number of squares crossed is affected when the diagonal crosses exactly through a lattice point in the grid. Students may also recognize that some relationship exists between when the diagonal will cross an interior lattice point and the slope of the diagonal in the grid.

We’ll return to this in our next PTP, with some more reasoning approaches, but this should provide a start for students to get to the bottom of what’s going on.

More Pondering:  

Recall that the March Problem to Ponder asked about the number of interiors of squares that a diagonal would cross in a rectangular grid.

Last month in our ponderings we saw that for every row in our grid, the diagonal crosses a square, and also for every column in our grid, the diagonal crosses a square. This makes sense because the diagonal has to cross through every vertical grid line and every horizontal grid line as it passes from corner to corner. However when the diagonal passes through a lattice point, the total number of squares crossed is affected, because a corner point is on both a horizontal and a vertical grid line simultaneously.

Consider the examples below:

Clearly, the number of squares crossed is partly determined by the sum of the number of rows and columns. The pattern above indicates the following: 5 rows + 1 column yields 5 squares crossed; 5 rows plus 2 columns yields 6 squares crossed, 5 rows plus 3 columns yields 7 rows crossed—so it seems to be the case that the number of squares that the diagonal crosses in these grids is one less than the sum of the rows and columns, or (N + M) – 1 for an N ´ M grid. This works until we hit a case where the diagonal passes through some lattice points; consider the examples below:

Whenever the diagonal crosses lattice points, as in the 4 x 2, 4 x 4, and 4 x 6 cases above, it crosses both a vertical grid line and a horizontal grid line simultaneously but passes through only one new square, not an additional one for each grid line. Our conjecture for the number of squares touched by the diagonal needs a correction—it isn’t always (N + M) – 1 for an N x M grid, because we will double count some squares. We need to correct by the number of lattice points that the diagonal passes through. How do we know how many lattice points the diagonal of an N x M rectangle will pass through? Ponder on—we almost have it!

One More Ponder: 

Our original conjecture for the number of squares touched by the diagonal in a rectangular N x M grid needed a correction; it isn’t always (N + M) – 1. We needed to correct by the number of lattice points that the diagonal passes through. The number of lattice points that the diagonal passes through is determined by the GCD of (N, M). So, in general, a diagonal will pass through (N + M) = GCD(N, M). When N and M are relatively prime, our original formula with subtracting 1 works!

Consider the examples below. In the first four lattices, the dimensions are relatively prime to one another—that is, the only common divisor is 1. So the number of squares crossed is always N + M – 1.

In the next four lattices, the dimensions of the lattice have a common factor greater than 1.

So, the number of sides crossed will be, respectively,

5 + 5 – GCD(5, 5,) = 5 + 5 – 5 = 5,

4 + 2 – GCD(4, 2) = 4 + 2 – 2,

4 + 4 – GCD(4, 4) = 4 + 4 – 4 = 4,

and

4 + 6 – GCD(4, 6) = 4 + 6 – 2 = 8.