SLOG #8

Problem Solving Episode: Diagonals

Understanding the problem:
There is a rectangular grid with m rows and n columns. A diagonal line is drawn from the upper left corner to the lower right corner and it passes through certain number of grid squares. How many grid squares will the diagonal line cross through? This means to determine a formula for the number of squares using m and n.

Devise a plan:
Start small, and draw grids with different column lengths and rows to find a pattern between m and n, to figure out the number of diagonal squares by recording the number of squares the diagonal crossed through in a line. This was done by increasing the column lengths and rows by 1 and separating the odd, even, and mixed results.

Carry out the plan:
After drawing several grids, I was able to come up with the equation that the number of squares, x, is equal to the sum of the number of rows and the number of columns subtracted by the difference of the greatest common divisor of m and n. Algebraically, x = m + n - gcd(m,n). I determined this by observing the pattern for odd values of m and n, even values of m and n, and mixed values.
The calculations I used to determine the formula was:
d = m + n - s, where d was the missing difference.
Then I observed the values for d and realized that it was the gcd of m and n that resulted in the value of d.

Look back:
Although my plan wasn't the most efficient or organized, I was able to reach the final result after doing a few calculations using m and n.