Problem Solving Episode

Problem:

Source: Wagon, Stan. MathForum. Problem of the Week 1001: Rectangles In A Staircase. 2004.
(http://mathforum.org/wagon/spring04/p1001.html)

Consider the 2x2 staircase made using 1x1 blocks. This 2x2 case contains 5 different rectangles in total (1x1 squares are also rectangles). What can you say about the total number of rectangles for an nxn staircase? Use your finding s to find the number of rectangles in a 10x10 staircase.




1) Understanding The Problem:
The problem is asking us to determine the number of rectangles that are present in a staircase made with 1x1 blocks, where 1x1 squares are also included as rectangles. This means that rectangles of allowed by the staircase must be included. There are no restrictions on the types of rectangles we are allowed to include in our calculations. As an example, the number of rectangles in a 2x2 staircase is given.

2) Devising A Plan:
By drawing different sized staircases and looking at the rectangles that they contain we can see that each staircase with length n, where the length is equal to the height, contains staircases of smaller lengths. My first idea is to think of the number of rectangles in each staircase recursively in terms of the number of rectangles in smaller cases. Along with this, another pattern present.
The number of rectangles in each staircase can be divided into three categories. The first category contains rectangles with a length that is greater than the height. The second category contains rectangles with a height that is greater than the length. The final category contains rectangles of equal height and length. Since the length of each staircase is equal to its height, there is symmetry in the way each staircase is constructed. If we construct a staircase of arbitrary length and count only the number of rectangles in the first category, we find it is equal to the number of rectangles in the second category. Upon noticing this equivalence in the number of rectangles, I decided to try and represent each staircase with a matrix to illustrate this pattern. The matrix design for a staircase of length n is as follows:


1x1 1x2 1x3 … 1xn
2x1 2x2 2x3 … 2xn
3x1 3x2 3x3 … 3xn
. . . .
. . . .
. . . .
nx1 nx2 nx3 … nxn

where 1x1 represents the total number of rectangles of size 1x1 and so forth. So the total number of rectangles is just the sum of the entries in the matrix.

Writing each staircase in this form may make it easier to determine patterns between the numbers of rectangles of equal size for various staircases. The equivalence of the first two categories means that we will end up with a symmetric matrix for each staircase representation. Therefore it is only necessary to determine a pattern between the upper triangles of various matrices. Once a pattern is found, the entire matrix for a staircase can be written and the total number of rectangles can be calculated.

3) Carrying Out The Plan:
To count the number of rectangles of a certain length and width, say i x j, we use an inductive approach. Assume that our original staircase has z rectangles of size i x j. To increase the length of a staircase by 1 unit, we simply add another column to the end of the original staircase with one more 1x1 block on the top. Since a new column is added, every row that contains an i x j rectangle is now able to construct one more, using the blocks in the new column. Also, the row of the staircase that was originally j-1 units long is now j units long. So one more rectangle of size i x j can be created including the blocks in the new row. Altogether the new staircase has an addition of (z+1) rectangles of size i x j. Using this approach, the matrices for the first four staircases are determined:

1 by 1: [1]

2 by 2:
[3 1
1 0]

3 by 3:
[6 3 1
3 1 0
1 0 0]

4 by 4:
[10 6 3 1
6 3 1 0
3 1 0 0
1 0 0 0]

There is an apparent pattern between the matrices of the first four staircases. Traveling along the rows of the matrix, beginning with a 1-entry, consecutive entries increase with the pattern 1 + 2 + 3 + 4 the sum of ….n for some natural number n. In the first row n is the length of the staircase. This sequence has the formula S = [n(n+1)]/2. Since the matrix is symmetric, this sequence is repeated in the columns as well. Therefore the sum of the entries a matrix can be written as the formula
[sum_(x = 1)^n expr(sum_(y = 1)^x expr(y(y + 1)/2))], where n is the length of the staircase.

So a staircase of length n has
[sum_(x = 1)^n expr(sum_(y = 1)^x expr(y(y + 1)/2))] rectangles.

So a 10x10 staircase has 715 rectangles.

4) Looking Back:
The solution obtained seems sound. Using the summation formula I correctly calculated the number of rectangles in the first four staircases which are 1, 5, 15 and 35 respectively. I checked these numbers by manually taking the sum of all the entries in each matrix. I’m sure that this is not the only method used to solve this problem. I used the matrix interpretation of the staircase because I believed it would enable me to see a pattern more easily. It turns out my method worked very well. It didn’t take very long for me to notice the sequence. If I conduct a search of this problem and similar ones, I’m sure I will find other methods used to solve it. I can use those methods to check my results.

Divide and Conquer is conquering me.

I'm currently studying for test 2 and I am reviewing the lecture slides and the examples in the text. I'm a little bit confuzzled about the divide and conquer example that was given in lecture regarding the time complexity of MergeSort. I think I understand why monotonicity is used here to prove that the counting method can be applied for all integers that are not of the form 2^k. In the scope of this problem it works because we are proving the inequality T(n) < Xlog_2(n). This can easily be proved for the special case and then monotonicity is used to show that for any natural number that is not of the form 2^k is less that some natural number that is and consequently satisfies the inequality as well. I'm hoping I have the right idea. It makes sense but this method can only be used when proving an inequality. I hope I have the right idea. Writing it out seems to help me make more sense of it. I should check the slides again.

A2 Graded. HOORAY? BOO?

Actually, it's a "Hooray" for my partner and I. We were both really worried about the first problem involving ternary trees. Instead of finding a formula, we developed a recursive method in python to count the number of configurations of ternary trees. Then we developed a pre-condition and post-condition for our method and proved its correctness in regard to our conditions. We got a pretty good mark for that question, so I'm happy. Hmm... we should probably show our proof to Danny. I'm sure he's interested to see how we proved our algorithm considering it took us forever and a day to come up with it in the first place.

Recursion Formulas

I'm currently studying for the first term test in 236. I'm not sure if Danny is going to include some questions regarding recursion formulas. I believe the focus of this test is to determine our ability to apply the basic rules and properties of mathematical induction. If that's the case, then there is a good chance that some recursive methods may show up since they are basically applications of the properties we learned. So I'm gonna study as much of it as I can.

Like simple and complete induction, recursion requires you to look for patterns between cases to create a general formula and prove it. However, I've noticed that these patterns can sometimes be difficult to see. I think the main reason for this may be the fact that a pattern doesn't always take the form of an equality. Many of the examples from previous weeks require us to find and prove equalities. Recursion requires you to look at questions differently. Right now, I still have the tendency to look for an equality. So I take a bit longer to figure out recursive patterns than I would others. I'm confident that I will be able to perform this kind of induction. After all, the concept is still the same. It's just going to take a little getting used to. That means I've got a lot more studying to do if I want to feel confident about writing the test.

Assignment 1 Reactions

Finally, my first post; and just in time. I just returned home from school after finishing and submitting the first assignment for this course. After struggling with the formal write -up of question 2, both my partner and I agree that it is is lot more confusing than we had anticipated. We found an algorithm for the menus and we knew what we had to do to prove that it works. The difficult part was transforming our ideas into a proof that is mathematically sound and that makes sense the first time it's read. I'll admit we would have had an easier time if we had just proved our findings in plain English. Personally, I kind of prefer to use mathematical language and symbols within proofs whenever I can. I don't know. I guess first year Calculus has sort of brainwashed me. At least no one can say I didn't learn anything.

Speaking of learning, Danny explained to me a way in which I can combine English with mathematical language to help explain difficult concepts or operations in proofs. Basically, you just create your own symbols. For instance, in question 2, my partner and I needed to write a set in reverse with a new element added to each of it's existing elements. This is an operation for which there is no notation. So, under the permission of Danny, we made our own notation. We just created an operation, A for instance, and explained what it does in English. Once established we were free to use the operation like we would use any other mathematical symbols. Problem solved. I don't know how we would have finished the write-up of this proof without this technique. This is definitely something I'm going to want to use again.