Who knew that Chapter 0 would have problems! Anyway ...
I saw this problem before in a math competition without proof - mugged up the formula then, didn't understand it, so promptly forgot it again.
Hopefully I will understand it this time.
This is the (very slightly edited) raw thought. The train of thought is intact.
Squares (m=n) are not interesting because things are so orderly there - diagonal passes through vertices. Incidentally answer = A = m = n.
So let's deal with rectangles. The smallest rectangle is m=1, n=2. But one has to suspect that m=1 leads to some special case without giving us much insight. So let's try m=2, n=3. Drawing it in Excel (see picture below), I see the answer is 4. The reason seems to be that all squares in vertical direction and all squares in horizontal direction needs to be touched - hence the answer is m+n. But wait, that is not true - the answer really is m+n-1. The reason is we double-counted the first (bottom-left) square. So there is the first cut of the formula:
At this point I am realizing that I do not fully understand why two squares (bottom-left and top-right) are not double counted. Call this Doubt 1. But I am going to let it slide for the moment (hence the numbering of doubts) - because there is a bigger realization, and that is that the square case is very interesting. For m=n=2, the answer is 2 and not 4. This is because diagonal passes through vertices of little squares, and each little square counts in both the vertical and horizontal direction. Obviously this has to do with diagonal passing through vertices of little squares.
I need to understand the case then where m = nk, k>1 and integer. This is not a square, but the diagonal sometimes cross vertices. Set m=2, m=6 (4 is also 2^2, so skip it). Draw it in Excel. True answer = 6. m+n-1 = 7. But ... the diagonal goes through the 'middle' vertex - and the suspicion is that's where we lost the second little square. Now I get it - when the diagonal touches the 4th tile - that tile is counted both in the horizontal direction and the vertical direction. So there it is then (and we have solved Doubt 1 as well): "when the diagonal continues away from a vertex then the next tile is double counted, so we subtract one the sum.". For Doubt 1, the diagonal started from the bottom-left vertex (hence the -1 there), but it did not continue after the top-left vertex (no subtraction). So the new formula is:
The rest is details. The number of intermediate vertices touched = k = gcd(m, n). But our m=nk is not the best example. We need, m=rk, n=sk. You can think of this as k x k tiling, each tile r x s. There are now k vertices the diagonal continues from (think of medium sized square tiles). So,
I saw this problem before in a math competition without proof - mugged up the formula then, didn't understand it, so promptly forgot it again.
Hopefully I will understand it this time.
This is the (very slightly edited) raw thought. The train of thought is intact.
Squares (m=n) are not interesting because things are so orderly there - diagonal passes through vertices. Incidentally answer = A = m = n.
So let's deal with rectangles. The smallest rectangle is m=1, n=2. But one has to suspect that m=1 leads to some special case without giving us much insight. So let's try m=2, n=3. Drawing it in Excel (see picture below), I see the answer is 4. The reason seems to be that all squares in vertical direction and all squares in horizontal direction needs to be touched - hence the answer is m+n. But wait, that is not true - the answer really is m+n-1. The reason is we double-counted the first (bottom-left) square. So there is the first cut of the formula:
A = m + n - "double counted squares"
At this point I am realizing that I do not fully understand why two squares (bottom-left and top-right) are not double counted. Call this Doubt 1. But I am going to let it slide for the moment (hence the numbering of doubts) - because there is a bigger realization, and that is that the square case is very interesting. For m=n=2, the answer is 2 and not 4. This is because diagonal passes through vertices of little squares, and each little square counts in both the vertical and horizontal direction. Obviously this has to do with diagonal passing through vertices of little squares.
I need to understand the case then where m = nk, k>1 and integer. This is not a square, but the diagonal sometimes cross vertices. Set m=2, m=6 (4 is also 2^2, so skip it). Draw it in Excel. True answer = 6. m+n-1 = 7. But ... the diagonal goes through the 'middle' vertex - and the suspicion is that's where we lost the second little square. Now I get it - when the diagonal touches the 4th tile - that tile is counted both in the horizontal direction and the vertical direction. So there it is then (and we have solved Doubt 1 as well): "when the diagonal continues away from a vertex then the next tile is double counted, so we subtract one the sum.". For Doubt 1, the diagonal started from the bottom-left vertex (hence the -1 there), but it did not continue after the top-left vertex (no subtraction). So the new formula is:
A = m + n - "no of vertices touched except the last one"
The rest is details. The number of intermediate vertices touched = k = gcd(m, n). But our m=nk is not the best example. We need, m=rk, n=sk. You can think of this as k x k tiling, each tile r x s. There are now k vertices the diagonal continues from (think of medium sized square tiles). So,
A = m + n - gcd(m, n)
Picture of Excel spreadsheet:
