- understanding problems:
When i draw a line from a upper left to the lower right corner (the diagonal) of the rectangle consists of square grids, i need to find the number of squares that the line crosses. For example:
the shaded squares are the ones crossed by the line drawn from the upper left to right bottom corner.
-Devise a plan
Let's say n is the number of squares in rows (horizontal) of the rectangular grid, and m is the number of squares in columns(vertical) of the rectangular grid. The example provided above shows the rectangular grid of m=4 and n=6 and the number of squares crossed by the line is 8. We can try different combinations of m and n. Then, see the pattern!!
-carry out the plan
I have tried many times and produced the chart of every different combination that ranges from m=1/n=1 to m=10/n=10. The cells in the interior, those other than upper edge of the numbers and left edge of the numbers, represent the number of squares crossed when i drawn a diagonal line from top left to the bottom right. Therefore, to illustrate by looking at the chart we can see when m=3 and n=5 the number of squares crossed is 7 and m=6 and n=7 the number of squares crossed is 12 and so forth.
|
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
|
10
|
10
|
|
3
|
3
|
4
|
3
|
6
|
7
|
6
|
9
|
10
|
9
|
12
|
|
4
|
4
|
4
|
6
|
4
|
8
|
8
|
10
|
8
|
12
|
12
|
|
5
|
5
|
6
|
7
|
8
|
5
|
10
|
11
|
12
|
13
|
10
|
|
6
|
6
|
6
|
6
|
8
|
10
|
6
|
12
|
12
|
12
|
14
|
|
7
|
7
|
8
|
9
|
10
|
11
|
12
|
7
|
14
|
15
|
16
|
|
8
|
8
|
8
|
10
|
8
|
12
|
12
|
14
|
8
|
16
|
16
|
|
9
|
9
|
10
|
9
|
12
|
13
|
12
|
15
|
16
|
9
|
18
|
|
10
|
10
|
10
|
12
|
12
|
10
|
14
|
16
|
16
|
18
|
10
|
- Look back/ Acknowledge when and how, you're stuck
Ok! now we have the data let's see what pattern i can produce. Just by looking at the chart I had NO IDEA what kind of pattern would produce the table like that... (I was like -_-??) Danny gave hint consider the cases when n=m+1 and when both n and m are even numbers. Hmm... yes, indeed, i found reasonable portion of them have the formula of : #of square crossed=m+n-1 for example (m=10 and n=9) and the even numbers did not agree to that formula... But, i noticed in the case of even numbers the line that is drawn diagonally from upper left to bottom right crosses one of the vertex of the square and there is actually two rectangular grid associated with it. For example, in the example shown in the very top
there is actually two rectangular grid of m=3 and n=2. Therefore, you subtract by 2 instead of 1 to obtain: #of squares crossed= m+n-2
However, there are still lot of exceptions how would you explain cases like m=6 and n=9? number of square crossed cannot be produced by the formula: #of square crossed= m+n-1 or #of square crossed= m+n-2. for that the answer should be 12 but each of the formula produces 14 and 13 respectively.
After playing around with numbers I have found out the final solution to this problem is that
# of square crossed= m+n - k, where k is the greatest common factor of m and n.
For example, in the case of m=6 and n=9 the greatest common factor of both 6 and 9 is 3. Therefore,
# of square crossed= 6+9-3
= 12!!
= 12!!
other cases like
m=2 and n=7, greatest common factor for both 2 and 7 is 1!
# of square crossed= 2+7-1
=8!!
m=2 and n=10, the greatest common factor for both 2 and 10 is 2.
# of square crossed = 2+10-2
=10!!
=10!!
FINALLY, the formula for this is # of square crossed = m + n - k , where k is the greatest common factor of n and m
