Tuesday, June 12, 2018

Shape-Counting Problem #3

How many triangles are there in these figures? I found this problem more challenging than Shape-Counting Problem #1 and Problem #2. In this case I used a recursive problem-solving approach that led to a formula that I then proved using mathematical induction. Let's begin by introducing some terminology. How about we say that all the figures in the second column have two segments coming from the left or two left segments. Every figure in the third row has three right segments. And let's say that is the number of left segments and m is the number of right segments.

Look at the figures with n = 1 in the first column.
It's the triangular numbers again! I haven't found a shape-counting problem that doesn't involve the triangular numbers. Check out my explanations for the first two problems if you'd like more insight.
If n = 1, there are T(m) triangles.

Now look at the figures with n = 2 in the second column. The figure with n = 2 and m = 1 has already been dealt with through its mirror image in the first column, so let's jump to m = 2.
If we think of the figure as being split into an upper piece and a lower piece by the interior left segment, then we can count the triangles in the lower piece (blue), the triangles in the upper piece (red), and the triangles that overlap (green).
Notice that for the blue regions and green regions we get triangular numbers, but in the red region the number of triangles is just the number of right segments. Now that the general pattern has been illustrated, I will sometimes just color the regions and omit a thorough inventory of every triangle.
It looks like we're ready to write a formula for figures in the second column.
If = 2, there are 2T(m) + m triangles.

Let's advance to the third column (n = 3) and skip m = 1 and m = 2 since we've already covered their mirror images. Recursive thinking will really start to come in handy now. In everything that follows the blue region will be a figure for which we have already developed a formula, the red region will represent all the triangles outside the blue region, and the green regions will represent the triangles that overlap. Here's how it looks for n = m = 3.
The structure is similar for n = 3 and m = 4.
And I think we're ready for another formula.
If n = 3, there are 3T(m) + 3m triangles.

Once we're ready we can look at all the formulas we've written for the columns and see if we can figure out how n fits into the formula. For me personally, I had to work out the formula for one more column before really seeing the pattern. Here's how things turned out for n = 4.
I'd like to solve!
If n = 1, there are T(m) triangles.
If n = 2, there are 2T(m) + m triangles.
If n = 3, there are 3T(m) + 3m triangles.
If n = 4, there are 4T(m) + 6m triangles.
For any n, there are nT(m) + mT(n-1) triangles.

I was so delighted to yet again see my friends, the triangular numbers, this time as coefficients in a sequence of formulas. But I also thought the formula must be wrong, because it lacked symmetry between n and m. It turns out that there is symmetry after all, because
nT(m) + mT(n-1) = nT(m-1) + mT(n).

Proof by Induction
If n = 1, the number of triangles is T(m). In this case the formula gives
nT(m) + mT(n-1) = 1T(m) + mT(0) = T(m) + m(0) = T(m),
so the base case holds.
Suppose that if n = k, the number of triangles is kT(m) + mT(k-1). We want to show that if n = k+1, the number of triangles is (k+1)T(m) + mT(k).
By the induction hypothesis, there are kT(m) + mT(k-1) triangles in the blue region. There are T(m) triangles that can be formed by selecting two elements from among the m right segments and the base of the figure. Finally, for each of the k interior left segments there are m triangles that can be formed by using that interior segment and the left segment on the perimeter of the figure. Taking the sum of all these triangles we get
kT(m) + mT(k-1) + T(m) + km
= (k+1)T(m) + m(T(k-1)+k)
= (k+1)T(m) + mT(k).

Summary of Shape-Counting Problems #1-3
Here is a rough summary of the formulas for the first three shape-counting problems I've written about:
It's quite beautiful how the triangular numbers appear in all these formulas, and it's possible to gain a deeper understanding of all these formulas by thinking about the combinatorial meaning of the triangular numbers. My route to the last formula in particular was rather tortured. Can you see how to justify the formula just by taking combinations of line segments? Anyway, stay tuned... the most exciting shape-counting problems are yet to come!

No comments:

Post a Comment