October 10, 2020
When he was only seven years old, there was a well-known urban legend about the German mathematician Carl Friedrich Gauss performing a tour de force right in front of his classmates and teacher. The story goes that presumably during a lesson in arithmetic, Gauss's teacher challenged his class to an exercise in addition: \begin{equation} 1 + 2 + 3 + \dots + 100 = \quad ? \end{equation} While Gauss's classmates immediately began scribbling on their notepads trying to solve the 99 addition problems, Gauss was not moving his pen. Instead, he stared at the expression and realized an interesting pattern: 1 and 100 make up 101, 2 and 99 make up 101, 3 and 98 add to 101, etc., all the way up to 50 and 51. It seemed that if one examined the terms from both ends, the elements involved would sum to 101. Then, all he had to do was to count how many pairs of "101"s appeared in the expression, which was 50, and 99 additions became one simple multiplication: \begin{equation} 1 + 2 + 3 + \dots + 100 = 101 \times 50 = 5050 \end{equation} Gauss arrived at the correct answer before his peers even made it past 20.
Of course, nowadays the result from the previous anecdote is simply known as the "Gauss Formula", which also works if the number of terms in the addition expression is odd instead of even. Namely, the sum of the first \(n\) natural numbers can be expressed as: \begin{equation} \sum_{k=1}^n k = \frac{n(n+1)}{2} \end{equation} He would end up contributing immensely in the field of mathematics throughout his life, having many more things named after him, and even be crowned as the "Prince of Mathematics" (Latin: Princeps mathematicorum). Furthermore, he would later show how his original "Gauss Formula" can also be proven using induction. However, induction is not the point of this blog. What I want everyone to learn is that sometimes it pays to take a step back, think a bit, and see your work cut in half (or more!). Thinking often is also a crucial component in developing habits to think critically, which as I echo here from my blog introduction, will be the tool that humanity will have in fighting for the advancement of our species. In math, as it is in life, there will be situations and problems where one way of arriving at the answer will be to use brute force. When impelled to do so, one would often discredit taking a step back to think about the problem first and instead immediately set out on the tedious task of taking the longest route to the answer. Doing so is not only physically and mentally draining and prone to errors, but one also misses out on the opportunity to discover something new and marvelous in the process. Sometimes knowledge is unearthed from solving a completely different set of problems, if only those problems are tackled using elegant solutions that would not have otherwise arose without a little thinking.
Let me illustrate this point by solving together the following problem. No advanced math, let alone calculus, is required.
"How many rectangles are there in an \(n\) by \(n\) grid of squares? (Note: squares are rectangles too)."
In the grid above for example, we have an 8 by 8 grid of squares, which for simplicity reasons, I will just call the grid a "chessboard". In order to make a rectangle from the chessboard, we need to trace out four grid lines to form the four sides of a rectangle, like so:
As you can see, we made a 2 by 3 rectangle in our chessboard by making the rectangle bounded vertically by columns 4 and 7 and horizontally by rows 2 and 4. One rectangle in the chessboard is considered distinct from another if those two rectangles are bounded by different coluns and/or rows (even if their areas are the same). So, back to our original question: how many distinct rectangles can we form from an \(n\) by \(n\) chessboard? Yes, brute force counting would certainly work in this case because this is a counting problem. So one without the patience to think first and rush into the work would take a very long time counting things up. This would probably not end well for the eager solver because for one thing, you are working with a generic integer \(n\), and for another, double-counting and missed counts are a real issue, and for the third matter, we can do a lot better if we just have thought more.
Before we get to how we can do well by thinking about the problem more, I would just like to share the fact that YouTube content creator "blackpenredpen" has a very intuitive solution to this problem:
I will quickly recap his solution. The making of a rectangle out of the \(n\) by \(n\) chessboard is a two-step process: first you select the column boundaries and then the row boundaries. For column boundaries, there are \(n\) columns to choose from and you need to pick out two distinct columns (because a rectangle has two vertical sides). Therefore, the number of ways to do it is \(\binom{n}{2}\). By symmetry, the same process works for picking out two distinct rows out of \(n\) rows is also \(\binom{n}{2}\). Therefore, the total number of distinct rectangles that can be made out of the chessboard is: \begin{equation} \left[\binom{n}{2}\right]^2 = \left(\frac{n(n+1)}{2}\right)^2 + \frac{n^2(n+1)^2}{4} \end{equation}
However, usually in math there are more than one way of solving a problem, and while blackpenredpen's solution is quite intuitive, for one thing it does involve some advanced knowledge in combinatorics. Furthermore, if we explore the problem deeper, perhaps we can start to see things in a different light, which then would help us extend what we learned solving this problem to other knowledge domains. In such a case, I would be happy to show how thinking more goes a long way.
I evoked the Hungarian mathematician George Pólya in my previous blog posts about problem solving, and I find relevant to mention him again here. In his How to solve it series, Pólya mentioned 14 different strategies when it comes to solving math problems. Three comes to my mind for this problem:
The above three strategies are usually how mathematicians go about solving complex problems--play around with it, find a pattern (like how the seven-year old Gauss did), and generalize the pattern by seeing how solutions to smaller problems lead to solutions for bigger ones. Therefore, let us try a few values for \(n\), starting with the smallest possible values.
| \(n\) | \(r(n)\) |
|---|---|
| 1 | 1 |
| 2 | 9 |
| 3 | 36 |
Here I let \(r(n)\) denote the number of distinct rectangles formed from an \(n\) by \(n\) chessboard, a.k.a. our answer. I encourage all readers to try out the values for 1, 2, and especially 3 to see for yourself the corresponding values for \(r(n)\) given. One observation is that \(r(n)\) seems to be a perfect square, which came to be of no surprise given blackpenredpen's solution. However, while I am finding a pattern and trying to turn the problem into smaller parts, looking at \(r(n)\) does not seem to help me, because the perfect squares in \(r(n)\) does not seem to tie with \(n\) that well:
| \(n\) | \(r(n)\) |
|---|---|
| 1 | \(1^2 = 1\) |
| 2 | \(3^2 = 9\) |
| 3 | \(6^2 = 36\) |
Aside from \(n = 1\), the fact that \(r(2) = 3^2\) and \(r(3) = 6^2\) just seemed to be lacking a direct connection between \(n\) and \(r(n)\). Therefore, as part of playing around, the next logical step, for me anyways, was to look at the difference between the \(r(n)\)'s, and more specifically, between consecutive \(r(n)\)'s. For completeness here, we'll let \(r(0) = 0\) since you cannot make any rectangles from a non-existent chessboard. \begin{align} r(1) - r(0) &= 1 - 0 = 1 = 1^3 \\ r(2) - r(1) &= 9 - 1 = 8 = 2^3 \\ r(3) - r(2) &= 36 - 9 = 27 = 3^3 \\ \end{align}
Aha! It seems that we have found a much more connected pattern between \(r(n)\) and \(n\) by looking at the consecutive differences than looking at things directly. It seems that: \begin{equation} r(n+1) - r(n) = (n+1)^3 \end{equation} Ultimately, that's how mathematical discoveries are created. A bunch of child-hearted numberphiles playing around, finding patterns, getting an intuition, and finishing off with a rigorous proof. We seemed to have found a pattern--let us intepret the pattern first to see if it makes sense, then let us set about proving it.
So, what does our hypothesized equation mean? Going from an \(n\) by \(n\) chessboard to that of \(n+1\) by \(n+1\), our equation means that the number of new rectangles created is equal to \((n+1)^3\). Now let us dive deeper by the aide of a diagram (which is also one of the strategies mentioned by Pólya!).
And there. We. Go. The above diagram illustrates perfectly the difference equation pertaining to our pattern. We notice that if a rectangle is contained entirely within the \(n\) by \(n\) chessboard, then it is also contained in our new \(n+1\) by \(n+1\) chessboard. Therefore, if we know the value of \(r(n)\), we don't have to consider that rectangle again for our new chessboard! The diagram also illustrates what we mean by new rectangles. The definition of a new rectangle created is one that contains at least one of the new squares introduced by upping the dimensions of our chessboard--i.e. containing at least one of red, green, or black squares.
Before I continue, let me denote the red squares as "row squares", because they are appended to each row of the old chessboard and considered as such because they are part of the \((n+1)\)st column. Similarly, I am denoting the green squares as "column squares" because they are part of the \((n+1)\)st row. For the black square that is not adjacent to the old chessboard, it is, by our definition, both a row and a column square.
So, our problem now becomes, instead of counting the total number of rectangles in our chessboard, we are counting the number of new rectangles only. Assuming the solution arrived at an earlier stage and only addressing the new ones are also the inspiration behind dynamic programming in computer science, so already with critical thinking and looking at the problem in a new light, we can see how that can be extended to other fields of math and science.
Let us first count the new rectangles involving the row squares, which are the red and black squares. There are three search dimensions:
It makes sense, since a rectangle has a width and height, and we can draw our rectangle anywhere in the chessboard. When we have multiple search dimensions, it often helps to fix all but one and look at the sole changing dimension for patterns or clues. In this case, let us fix the height to be 1 unit, and let us only look at rectangle formed in the first row, and look at how many \(x\) by 1 new rectangles we can form at the top of the chessboard.
Well, the answer is \(n+1\) new rectangles. To see this, just let the red square in the first row be at the end of the new rectangle. We can prepend between 0 and \(n\) squares (inclusive) from the old chessboard at the top row in front of the red square to form our new rectangle, so the answer is \((n+1)\).
By symmetry, there are nothing special about the rows, so fixing "height" to be of 1 unit, the total number of new rectangles we can form anywhere in our \(n+1\) by \(n+1\) chessboard is simply: \begin{equation} (n+1) \times (n+1) \end{equation} Here I don't combine the two \((n+1)\) parts of the expression into a square term because those two \((n+1)\)'s are different in meaning. One \((n+1)\) is the number of height-1 rectangles we can form in a given row, and the other \((n+1)\) is how many distinct rows in which we can form the new rectangles. The latter will change as the height changes. To see this, now we let height to be 2 units. How many rows can we form height-2 rectangles in our \(n+1\) by \(n+1\) chessboard? The answer is \(n\) rows because we cannot start creating our height-2 rectangles on the last row. Similar reasoning leads to the fact that there are \(n-1\) rows in which we can form our height-3 rectangles, \(n-2\) rows for height-4 rectangles, and so on, until there is only 1 row to form our height-\((n+1)\) rectangles, which would span the entire height of our chessboard. Therefore, the total number of new rectangles that we can form entirely out of our new row squares (the red and black squares in our diagram) is: \((n+1)(n+1) + (n+1)n + (n+1)(n-1) + \dots + (n+1)\), which we can write as: \begin{align} \text{Answer} &= (n+1)\sum_{k=1}^n k \\ &= (n+1)\left[\frac{(n+1)(n+2)}{2}\right] \\ &= \frac{(n+1)^2(n+2)}{2} \end{align}
Notice how our drive to think and find patterns gets rewarded when we obtain an expression that can be simplified further via the Gauss Formula, which the Prince derived through pattern finding as well!
By symmetry, the number of new column rectangles that we can create, which are the ones containing the green and black squares, is also \(\frac{(n+1)^2(n+2)}{2}\). Combining our results, the total number of new rectangles, which are defined as the ones containing the red, green, and black squares, becomes: \begin{align} \text{Answer} &= \frac{(n+1)^2(n+2)}{2} + \frac{(n+1)^2(n+2)}{2} \\ &= 2 \frac{(n+1)^2(n+2)}{2}\\ &= (n+1)^2(n+2) \end{align}
However, let us put on our critical thinking hats and try to see whether we are done here. Is our answer for number of new rectangles created really \((n+1)^2(n+2)\)? If we think carefully, we can see that we double-counted here. Remember that our sole black square is both a row and a column square, so when we derived the number of new rectangles involving row and column squares, the ones that involve the black square got accounted for twice. We can summarize our findings with a Venn diagram.
So our answer is actually \(|A\cup B|\), or the number of elements in the union of the new rectangles created via row and column squares. This is same as adding up the total number of elements in both sets and subtracting the intersected members, i.e. the double-counted rectangles. In other words: \begin{equation} |A\cup B| = |A| + |B| - |A\cap B| \end{equation} But what is \(A\cap B\)? It is the set of a new rectangles created involving both row and column squares. Since row squares and column squares can only be joined by the black square, this set is equivalent to the set of all new rectangles that can be created if it contains the black square. So now we only need to worry about how many new squares we can create that contains the black square. This counting is now very straightforward, since the rectangle's location is fixed. Only dimensions of this new rectangle can vary and even then, there is only one possible rectangle per dimension, since the lower right square of the rectangle must be the black square (please try out yourself to see!). Therefore, since there are \((n+1)^2\) possible dimensions in our \(n+1\) by \(n+1\) chessboard, \(|A\cap B| = (n+1)^2\).
Putting everything together: \begin{align} \text{Number of new rectangles created} &= |A\cup B| \\ &= (|A| + |B|) - |A\cap B|\\ &= (n+1)^2(n+2) - (n+1)^2 \\ &= (n+1)^2(n+1) \\ &= (n+1)^3 \end{align} As desired. Therefore, indeed, we have: \begin{equation} r(n+1) - r(n) = (n+1)^3 \end{equation}
Since \(r(1) = 1\), by induction, we see that: \begin{equation} \boxed{r(n) = \sum_{k=1}^n k^3} \end{equation}
***
So we arrived at two answers for the number of rectangles in an \(n\) by \(n\) chessboard: one by looking at number of new rectangles created, and the other by using combinatorics from blackpenredpen. Which one is correct? Well, the answer is both! As mentioned from the beginning, there are often multiple ways in solving math problems, and each solution brings about new light to the problem that can also be extended to other fields. Here, by combining our two solutions, we see a very interesting fact: \begin{equation} 1^3 + 2^3 + 3^3 + \dots + n^3 = (1 + 2 + 3 + \dots + n)^2 \end{equation} This is the famous sum of cubes formula, in which the right-hand side is arrived by reverse engineering blackpenredpen's solution via the Gauss Formula (again!). The above equation can also be proven via induction (please try this!), but that is not the point of this blog. Through this very fascinating counting problem, I hope I can shed light into the fact that when we think critically when confronted with a problem instead of mindless delving into brute force work, not only do we make our work lighter, but we also uncover patterns that expand our knowledge and marvels at math and nature.
In the spirit of critical thinking and finding patterns, I challenge all my readers to the following problem, again involving a grid of squares:
"How many ways (distinct routes) can we take to traverse an \(M \times N\) grid of squares, if we can only travel down and right, and we start from the top left corner and finish at the bottom right? We can only turn (change directions) at an intersecting point in the grid."
I will reveal the answer next time!
If you solved the challenge problem, here is an extension--inside our grid network, there will be certain intersections in which you must visit during your journey from start to finish. In addition, there will be certain intersections in which you must avoid along your journey. Please describe a general solution for solving this extension problem, given the solution to the original challenge question.
