Last Week Problem Solving
Time gone by, this
is already the last week of this semester. As we are asked, we need to post a
problem solving. During this semester, I post my some problem solving
regularly, but when I talked to professor Heap, he told me to write some
challenging problems instead of tutorial questions or in-class questions.
Therefore, I started to redo a hard problem, which we also did in class, and
try to get some idea for it. This problem named diagonals, and this problem is
really interesting for me to solve it.
Here is the problem: You have a rectangular grid made up of m rows and n
columns. Draw a line from the upper left to the lower right corner. How many of
the grid squares will the line pass through the interior of? If you are told m
and n, can you calculate how many squares the diagonal will meet? Can you
derive a formula? Can you justify your formula? What about a rectangular
parallelepiped that is m rows by n columns by o layers?
It is easy to show in graphs. I am doing this problem start from the
base case, which both m and n equals to one.
Then I can write m = 1 n = 1 s = 1
(My graph cannot be shown in this bolger for some reason, but it works on my paper.)
If I keep making row become 1, in other words, fix m = 1. Then the diagonal line cross every rectangle. If the diagonal line cross only one rectangle, the angle between one side of the rectangle and the diagonal line is 45 degrees. When n = 2, the slope of the diagonal line decrease. If and only if slope of the diagonal line becomes zero, then there can be some rectangles are not crossed by this diagonal line. And there is no way to make slope of the diagonal line become zero, therefore, it cross every rectangle. In other words, when we fix m = 1, n equals to any number, and grid squares will be that number, which n equals to. For example, m = 1, n = 2, then there are two rectangles are crossed by diagonal line.
Now, lets fix n to be 1 and let m be some other numbers. This is another way to think about last paragraph. I mean only fix m or n equal to one, the answer is same. Because they are same, the only different is one is horizontal, and the other one is vertical.
After we complete the base case, then lets think more.
When we fix m = 2. When n = 1, it is same as our base case. when n = 2, then we have a 2 * 2 big rectangle, and the grid squares are two. Top right and bottom left are not crossed, and the slope of the diagonal line is 45 degrees. When n = 3, there is a 2 * 3 big rectangle. the the number of grid squares is 4. Top right and bottom left are not crossed. when n = 4, the number of grid squares is still 4. When n = 5, the number of grid squares is 6, when n = 6, the number of grid squares is 6. Let's organize those numbers, 2, 2, 4, 4, 6, 6... (the number of grid squares) it looks like repeat an even number twice and go to the next even number. Then I tried to count n = 7, as I supposed, the number of grid squares is 8 and when n = 9, the number of grid squares is 8.
Let us fix m = 3 now. when n = 1, the number of grid squares is 3, because of our base case. When n = 2, the number of grid squares is 4, when n = 3, the number of grid squares is 3. Until I got this answer, it surprised me. When we fix m = 2, the number of grid squares are keeping increasing. But in this case, it decreased when n = 3. When n = 4, the number of grid squares is 6. Surprisingly, t he number of grid squares is the number of grid squares is increasing again. WOW! How to know the next one only by looking those datas? It is impossible to find how many grid squares just by using those numbers. It took me few hours to think and graph to see what is going on here, but I get nothing helpful. So my day one, stops at there.
In day two, I was relooking at this problem, and it remind me that I cannot find anything helpful when I fix m = 3. By looking my old data, and rewrite my data, then I found something very interesting. This is few lines of my data:
1 2 3 4 5 6 ...
2 2 4 4 6 6 ...
3 4 3 6 7 6 ...
4 4 6 4 8 8 ...
5 6 7 8 5 10 ...
6 6 6 8 10 6 ...
... the number of grid squares is
Left column is same as top row, and there is a line number like diagonal line. As shown in my data, I mean the number of diagonal line is same as top row. So far, there are three line have same numbers, which is two green lines and a red line. As I found out, the numbers is symmetrical. In other words, when fix m = 1, it is equal to fix n = 1; when fix m = 2, it is equal to fix n = 2. This is really impressive for me. Although I cannot find a formula for this question so far, but I found this interesting table.
Then I am thinking about what is the formula for this question. It is really hard to figure out a formula, I think this for while, but get nothing. Is it possible to write a formula for a symmetrical data? But I cannot figure out it, I mean it, because I was thinking this for at least half an hour. It may be very short time to think, but during this 30 minutes, I get nothing useful. That is my problem solving for this week, it is different than my other easy problem solving, and I am enjoyed it.
In the end, I really love those hard and interesting questions which we did in class. It takes time to think and we can find some data are interesting. CSC165 is a kind of different course in computer science, but I like the way to think a problem and prove some problems. Well done for this semester, thanks for our professor Heap and my TA Lalla, thank you for teaching me those useful and interesting knowledge and helping me on assignments and tutorials. This is a fun semester, thank you.
(My graph cannot be shown in this bolger for some reason, but it works on my paper.)
If I keep making row become 1, in other words, fix m = 1. Then the diagonal line cross every rectangle. If the diagonal line cross only one rectangle, the angle between one side of the rectangle and the diagonal line is 45 degrees. When n = 2, the slope of the diagonal line decrease. If and only if slope of the diagonal line becomes zero, then there can be some rectangles are not crossed by this diagonal line. And there is no way to make slope of the diagonal line become zero, therefore, it cross every rectangle. In other words, when we fix m = 1, n equals to any number, and grid squares will be that number, which n equals to. For example, m = 1, n = 2, then there are two rectangles are crossed by diagonal line.
Now, lets fix n to be 1 and let m be some other numbers. This is another way to think about last paragraph. I mean only fix m or n equal to one, the answer is same. Because they are same, the only different is one is horizontal, and the other one is vertical.
After we complete the base case, then lets think more.
When we fix m = 2. When n = 1, it is same as our base case. when n = 2, then we have a 2 * 2 big rectangle, and the grid squares are two. Top right and bottom left are not crossed, and the slope of the diagonal line is 45 degrees. When n = 3, there is a 2 * 3 big rectangle. the the number of grid squares is 4. Top right and bottom left are not crossed. when n = 4, the number of grid squares is still 4. When n = 5, the number of grid squares is 6, when n = 6, the number of grid squares is 6. Let's organize those numbers, 2, 2, 4, 4, 6, 6... (the number of grid squares) it looks like repeat an even number twice and go to the next even number. Then I tried to count n = 7, as I supposed, the number of grid squares is 8 and when n = 9, the number of grid squares is 8.
Let us fix m = 3 now. when n = 1, the number of grid squares is 3, because of our base case. When n = 2, the number of grid squares is 4, when n = 3, the number of grid squares is 3. Until I got this answer, it surprised me. When we fix m = 2, the number of grid squares are keeping increasing. But in this case, it decreased when n = 3. When n = 4, the number of grid squares is 6. Surprisingly, t he number of grid squares is the number of grid squares is increasing again. WOW! How to know the next one only by looking those datas? It is impossible to find how many grid squares just by using those numbers. It took me few hours to think and graph to see what is going on here, but I get nothing helpful. So my day one, stops at there.
In day two, I was relooking at this problem, and it remind me that I cannot find anything helpful when I fix m = 3. By looking my old data, and rewrite my data, then I found something very interesting. This is few lines of my data:
1 2 3 4 5 6 ...
2 2 4 4 6 6 ...
3 4 3 6 7 6 ...
4 4 6 4 8 8 ...
5 6 7 8 5 10 ...
6 6 6 8 10 6 ...
... the number of grid squares is
Left column is same as top row, and there is a line number like diagonal line. As shown in my data, I mean the number of diagonal line is same as top row. So far, there are three line have same numbers, which is two green lines and a red line. As I found out, the numbers is symmetrical. In other words, when fix m = 1, it is equal to fix n = 1; when fix m = 2, it is equal to fix n = 2. This is really impressive for me. Although I cannot find a formula for this question so far, but I found this interesting table.
Then I am thinking about what is the formula for this question. It is really hard to figure out a formula, I think this for while, but get nothing. Is it possible to write a formula for a symmetrical data? But I cannot figure out it, I mean it, because I was thinking this for at least half an hour. It may be very short time to think, but during this 30 minutes, I get nothing useful. That is my problem solving for this week, it is different than my other easy problem solving, and I am enjoyed it.
In the end, I really love those hard and interesting questions which we did in class. It takes time to think and we can find some data are interesting. CSC165 is a kind of different course in computer science, but I like the way to think a problem and prove some problems. Well done for this semester, thanks for our professor Heap and my TA Lalla, thank you for teaching me those useful and interesting knowledge and helping me on assignments and tutorials. This is a fun semester, thank you.
