1. Understanding the problem
- We are given a rectangle/square of n m rows and columns respectively, and we draw a diagonal line from one corner to the other. We need to find how many grid squares the line passes through.
- We need to account for special cases such as when n or m are odd or even.
2. Devising a Plan
- Given the example, it seems that we could work out some sort of a pattern.
- My firsts thoughts guide me to create a table and record down different numbers of rows and columns to see if there is similarity between the values in terms of n and m.
- After evaluating the data I would see if we could get a formula that would satisfy both n and m on all occasions.
- I would sketch some visual representations to see if the formula works correctly.
3. Carrying out the plan
- The first thing we can obtain from the table is that when both n and m are the same, the number of squares.
- There is an obvious pattern going on but at first I couldn't seem to be able to generate a formula for it. However, after a bit of thinking I solved it. It used something that I haven't seen since elementary school (I don't recall using it after); finding the highest common factor. However, I ended up with 2 formulas and couldn't find a way to join them. Here they are:
- When there is a highest common factor between m and n, the formula for the total number of grid squares crossed by the line is m + n - the highest common factor. Lets take m = 4 and n = 8 for example. Total number of squares would be 8 + 4 - 4 which equals 8
- When there is not a highest common factor, the total number of squares is m + n - 1. m = 4 n = 5. Total number of squares 4 + 5 - 1 = 8 total squares; matches the table.
4. Looking Back
- I wasn't expecting the problem to take 2 different formulas to solve and I took a bit of extra thinking as I was trying to solve it all using one formula.
No comments:
Post a Comment