Problem Solving: Diagonals

On Friday Feb. 15, we were given the "diagonals" problem in class. It seemed easy enough at first. But, as it turns out, my initial solution was far from perfect.

The problem: Draw a diagonal in a rectangle of m rows and n columns. Find out how many of the grids the line passes through the interior of.

The plan: As with folding, make enough examples to find a pattern.

We drew rectangles from 1x1... 2x1... 2x2 up till 5x5, and from there devised a pattern:
   -for m is odd, the number of shaded squares is m + n - 1 if m != n
   -for m is even, the number of shaded squares is m + 2 [[(n-1)/2]] (where [[]] is the floor function) if m != n
   -for m = n, number of shaded squares is simply m or n.

I showed my solution to Professor Danny who informed me that there were problems with my solution involving multiples. So I made a bunch more examples and compiled that into a new chart.

	n
m		1	2	3	4	5	6	7	8	9	10
	1	1	2	3	4	5	6	7	8	9	10
	2	2	2	4	4	6	6	8	8
	3	3	4	3	6	7	6	9	10
	4	4	4	6	4	8	8	10	8		12
	5	5	6	7	8	5	10	11	12
	6	6	6	6	8	10	6	12	12		14
	7	7	8	9	10	11	12	7	14
	8	8	8	10	8	12	12	14	8		16
	9	9								9
	10	10			12		14		16		10

The 9 and 10 columns are incomplete because I ran out of space and didn't actually draw them. I noticed that the pattern was only broken when m was divisible by n or n was divisible by m. (but sometimes not even then).

It seems, from the exceptions I found in the chart I made (3x6 and 4x8) that the number of shaded squares is then equal to max(m,n), which also works for 2x4. So I think adding this condition, if m%n ∈ℕ then number of squares the diagonal passes through = max(m,n) would fix the pattern. 

Looking back: I didn't really get stuck anywhere, it was a fairly straightforward process, though I stopped working on it for a while after class. I still don't know if I have the complete solution (probably not, this did not take nearly enough time) but so far I didn't really get stuck.