Wednesday, April 18, 2018

Shape-Counting Problem #1

I've used these shape-counting problems as "Do Now" exercises, and students are always excited to work on them and argue about them. Recently I have been investigating whether any of these problems are worth spending more time on. Could my students generalize them and write formulas? Could these problems motivate heavy mathematical machinery like induction? In a series of posts I will attempt to answer these questions. The problem above recently got a lot of attention on social media, so I will start with this one. "Spoilers" follow!

First we'll introduce some terminology. Let's say the above triangle has 3 "horizontal" segments and 4 "vertical" segments. The problem can be generalized as "how many triangles are there in a triangle with h horizontal segments and v vertical segments?" We then get a two-dimensional array of problems:
The problems in the left column are the easiest to solve. The number of triangles is equal to the number of horizontal segments, h. The next easiest problems to solve are the ones in the top row. Working out each problem we may notice that we get the triangular numbers. Specifically, the number of triangles in the triangle with v vertical segments is the (v - 1)th triangular number, which I'll denote T(v - 1). It's cute that we're dealing with triangles and the triangular numbers pop up. However, it really has nothing to do with triangles. The answers to these problems are also the triangular numbers:
The reason we get triangular numbers can be seen by thinking of the triangular numbers combinatorially. Each triangle (or rectangle) is formed by selecting two vertical segments. So the number of triangles is "v Choose 2". And "v Choose 2" gives us the triangular numbers as this picture illustrates:
We've figured out the top row and the left column in our original array of problems. Now we just need to put these two solution methods together to figure out the rest. It turns out that all we have to do is multiply the answer for the leftmost column by the answer to the top row. So a triangle with h horizontal segments and v vertical segments contains hT(v - 1) triangles. Why? Notice (as one of my students did) that the original problem breaks down into three equivalent problems from the top row:
So the answer to the original problem is 3T(4 - 1) = 3T(3) = 3*6 = 18. In general, a triangle with h horizontal segments breaks down into h copies of the problem from the top row. It would be possible to use mathematical induction, arguing during the induction step that adding another horizontal segment adds T(v - 1) triangles, but I think that would be overkill when we can just use multiplication.

Thanks for reading! If you generalized, formalized, or solved the problem differently or have any other ideas, I would be excited to hear from you. Another shape-counting problem will be coming soon!