Follow up to the Diagonals Problem

In my solution to the diagonals problem, I felt like I wasn't able to adequately explain how I got from the numbers to the final equations. This is because I'm not too sure myself, it was the product of trial-and-error, luck and a bit of inspiration.

In his post, Tim does a great job of showing his thinking that led him to the same formula I got. Also, he posted code to a python program that takes the dimensions of the grid as input and returns the number of squares the diagonal crosses. The trickiest part of the program was the helper function for determining the greatest common factor of m and n. I hadn't thought that far... I was hoping python would have a built-in function for that!

This will be my last post for the course. It was interesting, challenging and I feel well prepared for CSC 236 next semester. I'm a bit embarrassed that I forgot how to take derivatives during the final, but I'm going to chalk that up to exam time stress.

Thanks for reading!

Problem Solving: Diagonals

If there is a grid of squares with a certain number of rows (m) and columns (n), is it possible to determine the number of squares a line will go through if drawn from top left corner to the bottom right? This was a problem given to us in a problem solving class and I would like to discuss how I went about solving it. 

The problem: 

• Input: two natural numbers that describe the length and height of the grid (m x n).
• Output: the number of squares that a diagonal crosses from the top left corner to the bottom right corner of an m x n grid (s). 

The Plan: Draw some m x n grids and diagonal lines. Look for patterns and interesting cases. 

5 x 3, s = 7; 5 x 8, s = 12

First observations:

1) the order of m and n doesn't matter. In the picture below, diagonals through 8 x 1 and 1 x 8 sections both cross 8 squares (blue in the picture below).

2) when m = n, you have a perfect square and s = m = n. A diagonal through an 8 x 8 grid crosses 8 squares, because it goes perfectly from the top left to bottom right corner of each square (green in the picture below).

So for ease of computing s, I can arbitrarily assign m as the smaller number/ odd number/ prime number. Whatever makes writing a function easiest. 

8 x 8, s = 8

I noticed that when m is divisible by n or vice versa, then s = max(n, m). However, this still leaves a lot of the combinations to solve, but it led me to notice that if m and n have the same factor, the line splits up into smaller sections. (i.e. 4 x 6 = 2(2 x 3). This means that you can multiply the number of squares the line passes through in the smaller section by the number of smaller sections (2 * (4 x 3, s = 6) that make up the large section (8 x 6, s = 2 * 6 = 12).

8 x 6 = 2(4 x 3)

Acknowledging when you're stuck: At this point I was a bit stuck. I knew how to determine s for certain specific cases, but there was still the problem of working out s when m and n only shared a common factor of 1. It was getting very complicated looking at grids with lines going all over the place. It was time for a new approach. I turned to just looking at the numbers to see if I could find a pattern. I created a table with values of n and m on each axis and filled in s values.

After staring a while at the numbers and trying out different ways of getting from m and n to s, I came across the equation s = n + m - 1. This seemed to work for the cases I hadn't solved for (i.e. when n and m only have a common factor of 1).

Looking back, I realized that a variation on this equation actually works for all cases, if the largest common factor (F) of m and n is found. Then the equation can be written as:

s = F(n\F + m\F -1)

where F is the largest common factor of m and n. In the end, it didn't matter if n or m were larger, smaller, even or odd.