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.

Answer: Given in Solution.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s