Week 12: Problem solving episode of diagonals problem

The rough work:

To summarize:

Understand the problem:

-You have a rectangular grid of m rows and n columns.
-m and n are positive whole numbers (1, 2, 3...).
-A diagonal is drawn from the upper left to the lower right corner.
-The diagonal touches some of the interior grid squares.

Problem: Calculate the number of squares x that the diagonal meets, given m and n.

Preliminary observations:
-The problem can be divided into smaller problems, in that if m and n have a greatest common divisor = gcd, then this rectangle can be divided into smaller rectangles with m' = m/gcd and n' = n/gcd.


Devise a plan:

-Start with rectangles with the smallest ratios of m:n such that their gcd is 1.
-"Extend" each rectangle once such that the rows are m + m and the columns are n + n.
-Find a pattern between x and m, n.
-Find a pattern between the smallest ratio rectangles and the extended rectangles.

Carry out the plan:

-Draw a lot of rectangles! See above.

Observations:
-For m = a and n = b, the x is the same as m = b and n = a.
-As predicted, "extending" each rectangle proportionally does not affect the slope of the diagonal.
-For a pair of m and n whose gcd is 1, x = m + n - 1.
-The relationship between x for the rectangle with said m and n pair and x' for the "extended" rectangle with m' = gcd * m and n' = gcd * n is: x' = gcd * x
-Then for any m and n, x = gcd ( m/gcd + n/gcd - 1) = m + n - gcd

The solution: x = m + n - gcd
where x = number of square grids
          m = rows
           n = columns
       gcd = greatest common divisor of m and n











Looking back:

My first attempt in the rough work did not lead me anywhere, and I had to go back and revise the plan. (The first attempt involved dividing the possibilities into several cases, such as m = n, m and n are odd, etc., extending each case, and finding a pattern for each case. However, I immediately realized that sometimes, extending the case where m and n are odd can lead to a case where m and n are even, so that patterns for these cases may not be very different.)

When I was drawing the rectangles, I did not notice at first that the pattern was m + n - 1 for the smallest rectangles. At first I thought only in terms of the largest of the two numbers, which I always chose to be n. Then x was always n + some number that increased with m. When I was finally done drawing and looked back over all the examples, the pattern became clear!