Tuesday, December 2, 2014

SLOG 11 December 2nd 2014

During the last CSC165 class, I worked on a problem called diagonal with a friend of mine.  The problem involves rectangles that are made of squares with 1 unit area.  The problem is that if a diagonal line cuts a rectangle from corner to corner, how many unit squares within this rectangle will remain intact and how many will be cut?

The first step was to understand all the known and unknown of this problem.  Because the rectangle is made of squares of unit length 1, that means if we know the length and width of the rectangle, we are able to calculate how many squares are in this rectangle.  The problem involves finding two numbers; the number of squares in the rectangle that isn't cut, and the number of squares in the rectangle that is cut.

The second step was to devise a plan.  Initially, the handout had a picture of a 4 by 6 rectangle, and i realized that the line intersects the mid point of the rectangle.  What this helped me realize was that the rectangle can be split into two identical 4 by 3 rectangles, which means if we can find out how many squares are cut in this rectangle, i can just double that number to find the number of squares cut in the 4 by 6 rectangle.  However, after thinking about this plan, i realized that if the rectangle had odd side lengths, then the rectangle cannot be cut into more rectangles evenly.  After this stumbling block, i got stuck on the problem for quite some time, thinking about the possible ways of splitting each rectangle into smaller components.  Then, i suddenly realized that the diagonal line itself splits the rectangle into two identical triangles!  My plan was then focused on trying to use what i know about the triangles to calculate how many uncut squares exist inside.

With the triangle, i know that i can calculate its area, but that wont help me very much because the area represents the entire surface of the triangle, not the area of each square plus the left overs.  After much brainstorming, my friend and i realized that the triangle reminded us a lot about integration.  We drew many triangles of varying base and heights, and then divided the triangle into unit squares to see which squares are cut and which are not.  For example, imagine a triangle of base 4 and height 2.










This triangle can be viewed as 4 columns with a slanted top.  If we can find the height of the shortest side of each column, then we can find out how many uncut squares are in that column.  Then, we just need to add up all of the uncut squares of each column to find the total number of uncut squares in this triangle, and multiplying that number by 2 will give me the number of uncut triangles in a rectangle with width and length equal to the base and height of the triangle.

How can we find the height of each column?  Well since we can calculate the slope of the triangle by (height/base), we can use the slope to find the height!  Referring back to the 4 by 2 triangle, the slope will be 2/4, which is equal to 1/2.  So starting from the right most column of the triangle, this column is actually a triangle itself.  That means its height on the right is (0 X 1/2) = 0, and its height on the left is (1 x 1/2) = 1/2.  So we know the height of the two sides of this column, but neither of them are above one, so we can conclude that there are no squares in this column.  Now lets move onto the second column from the right.  The short side of its height is (1 x 1/2) = 1/2, and the long side of its height is (2 x 1/2) = 1.  We know that one of its side is 1, but the other side is less than 1, so its impossible for a square to be in this column either.  On the third column, the two heights are 1 and 3/2.  Now, both sides have a height greater than 1, so that means there is a square in this column!  On the last column, the two heights are 3/2 and 2, and since the shorter side is greater than 1, that means there exists another square in this column.  That means the 4 by 2 triangle has 2 uncut squares, which means a 4 by 2 rectangle will have 4 uncut squares, and that (8-4) = 4 squares are cut by the diagonal line.

To summarize this solution, we have come up with a formula that has been tested with numerous triangles and have worked in all cases tested so far.



What we discovered was that if knowing the longer height of a column will give us the number of squares in the next column, because in the next column, this height will be the shorter of its two heights, and if this height can be rounded down to a whole number, then that number represents the number of squares in the next column.  In the formula above, l represents the length of a rectangle, which is the same as the base of the triangle cut from this rectangle.  W represents the width of the rectangle, which is also the height of the triangle.  (w/l) is the slope of this triangle, and i represents the the distance from the tip of the triangle to the next column height.  The floor rounds the height down to a whole number, and the summation adds up all of the number of squares.  The reason why i only goes up to the second last column height is because we only need the previous height to know the number of squares in the next column.

The blog of the student i worked with can be found here:
http://kenguoslog165.blogspot.ca/

His latest blog should be an account of how we solved this problem in his point of view.  Its worth checking out, as thought we arrived at the same conclusion, we had different approaches and methods that helped us get there.

No comments:

Post a Comment