Before I begin my problem-solving episode, I would like to first mention that the problem-solving section on http://zanecsc165.blogspot.ca/ was one of the most detailed (and awesome) post I've read.
But back to my problem...
Understanding the Problem:
But back to my problem...
Understanding the Problem:
I have a rectangular grid made up of m rows and n columns,
where m and n are whole numbers. Problem: If I draw a line from the upper left
to the lower right corner, how many grid squares does the diagonal line meet?
Given information: values for m and n
Unknown: number of squares the line passes
Devising a Plan:
-
The first thing to do is to try a couple of
examples. Consider the following cases:
Ø
m and n are both even
Ø
m and n are both odd
Ø
m = n
Ø
m is even and n is odd (and vice versa)
-
Take note of any patterns that seem to appear
→ What happens in special cases, such
as n = m + 1, or when m and n are both even?
→ Are there
cases when the problem scales down to some smaller rectangle?
-
From the patterns, try coming up with a
universal formula that works for all cases
Carrying out the
Plan:
We can see that in this special case (m = n), the number of boxes filled equal m (or n).
What about when m and n are both even?
When m and n are both even, notice that the pair (m, n) can
be reduced to a multiple of some numbers. For example: (2, 4) = 2(1, 2), (2, 6)
= 2(1, 3), and (8, 4) = 4(2, 1).
This means that whenever we see a pair of number that have a
common factor other than 1, we can factor out a number and scale down the rectangle.
In the case where (m, n) = (3, 9): notice that 3 can be factored out 3(1, 3).
Now let's consider when one variable is even, and the other is odd:
In the sets of numbers that I used, none of them could be factored. This means that when devising a formula, we have to take into account large rectangles that cannot be broken down into smaller ones.
Now that I have drawn sample rectangles, there are some prominent re-occurring patterns.
1. Large rectangles can be broken down into smaller ones if the set of numbers have a common factor that is not 1. When we factor out a some integer, let's name it variable k, we have k number of small rectangles with the dimensions (m/k, n/k). What does this mean? This means that by knowing how many grids the diagonal passes on the rectangle with dimensions (m/k, n/k), we can know how many grid boxes the line passes in the non-scaled rectangle (by multiplying the number of grids found in scaled-down rectangle by the integer k).
2. In special cases, such as n = m, we can automatically conclude that the number of grid boxes the diagonal goes through is equal to m or n. This makes sense visually as well.
3. There are rectangles where dimensions are not-so-friendly. We need a method where it would work ANY type of rectangle. Here is my method:
Assign x = n and y = m, then treat them as coordinates and plot them on a Cartesian plane. Draw a line starting from (0, 0) to (x, y). Now that we know two points, we can get the slope of the line. Put the line in y = mx + b form.
Plug in values for x = 1, x = 2, ..., x = n - 1, and get the corresponding y-values.
Now, take the ceiling of the y-value. Whatever the value the ceiling is, shade in the box to the right of the x-value (for clarification, refer to the example below). Notice that when x = 2, we shade in two boxes. This is because when x = 3, the ceiling of y increases one step to two. This means that there is one grid the diagonal is crossing in order to connect the two boxes.
We can now add up the number of boxes shaded in (and also add 1 to account for the box at (0, 0)). This gives us 6. In order to get the number of grids for the rectangle (4, 10), multiply 6 by 2 to get 12.
Looking Back:
I know that my method is not efficient. I'm having difficulty putting this method into a nice, one-step formula. In terms of correctness... so far it has worked for all examples that I have tried (including all of the cases mentioned in the planning stage). However, since I do not have a formula to sum this up, it would be extremely tiresome to calculate something like m = 150 and n = 200. I could possibly implement a python function using this line of thinking though.
Now that I have drawn sample rectangles, there are some prominent re-occurring patterns.
1. Large rectangles can be broken down into smaller ones if the set of numbers have a common factor that is not 1. When we factor out a some integer, let's name it variable k, we have k number of small rectangles with the dimensions (m/k, n/k). What does this mean? This means that by knowing how many grids the diagonal passes on the rectangle with dimensions (m/k, n/k), we can know how many grid boxes the line passes in the non-scaled rectangle (by multiplying the number of grids found in scaled-down rectangle by the integer k).
2. In special cases, such as n = m, we can automatically conclude that the number of grid boxes the diagonal goes through is equal to m or n. This makes sense visually as well.
3. There are rectangles where dimensions are not-so-friendly. We need a method where it would work ANY type of rectangle. Here is my method:
Assign x = n and y = m, then treat them as coordinates and plot them on a Cartesian plane. Draw a line starting from (0, 0) to (x, y). Now that we know two points, we can get the slope of the line. Put the line in y = mx + b form.
Plug in values for x = 1, x = 2, ..., x = n - 1, and get the corresponding y-values.
Now, take the ceiling of the y-value. Whatever the value the ceiling is, shade in the box to the right of the x-value (for clarification, refer to the example below). Notice that when x = 2, we shade in two boxes. This is because when x = 3, the ceiling of y increases one step to two. This means that there is one grid the diagonal is crossing in order to connect the two boxes.
We can now add up the number of boxes shaded in (and also add 1 to account for the box at (0, 0)). This gives us 6. In order to get the number of grids for the rectangle (4, 10), multiply 6 by 2 to get 12.
Looking Back:
I know that my method is not efficient. I'm having difficulty putting this method into a nice, one-step formula. In terms of correctness... so far it has worked for all examples that I have tried (including all of the cases mentioned in the planning stage). However, since I do not have a formula to sum this up, it would be extremely tiresome to calculate something like m = 150 and n = 200. I could possibly implement a python function using this line of thinking though.
No comments:
Post a Comment