Now one of Dave Richeson's students has brought up another tin ceiling problem. Here's the pattern:

The question the student asked was "How many triangles (of any size) are there total?"

I avoided reading the solution post, so I could work on it when I had time, but I had a suspicion I might not manage to find the time. Then a conversation began on the Math 2.0 list (aka Math Future) about problem-solving, and how cool it would be to have a written description of different people's thinking processes as they work through a problem. (Mike South wrote: "Something that may be of use is first person narrative of an actual problem solution by various people.") I mentioned that I was thinking about trying to solve this problem, and two group members jumped on it, and contributed their solutions/ thoughts (which I haven't really looked at yet). Linda Fahlberg-Stojanovska and Dani Novak each posted some cool stuff related to how they played around with it.

While I was on BART on the way to the Escape From the Textbook conference, I began work on the problem, and tried to write down everything I was thinking. It would be great to have this sort of thing from other people too. If you're interested, you may want to stop now, and go play. It was hard for me to remember to stop thinking about the problem and

*write down*what I'd just been thinking, but I think I captured most of it. (I have probably conveniently forgotten to write down some false starts and dead ends...) I was so engrossed in the problem that I almost missed getting off at Civic Center. I jumped up just in time, ran over to the Muni, and got back to work.

**My Process**

Saw the problem at Dave Richeson's blog, skipped the solution post. Counted 4 little triangles per square. Saw at least one bigger triangle. Stopped there.

In bed, decided to organize my counting by size of triangle.

On BART, using my graph paper notebook, I draw a picture like that above, that shows a 2x2 grid of squares. (Each square uses 4 of the graph paper squares.) I count 4 little triangles in each square. 4 squares makes 16 of those. I draw a little picture of that size triangle and next to it I write '=16'.

Making a triangle from 2 littles gives 16 also. (There are 4 ways to get one of these triangles in each square.)

4 triangles... Wait, can't I use 3? Nah. [Later thoughts in brackets: While typing, I double-check this by looking at a representative size 2 triangle, and trying to attach each adjacent triangle to it. None work.]

Back to 4. Orienting the first one with its hypotenuse along the left edge of the figure, I see I can't move it up or down. There's another just like it with its hypotenuse along the vertical midline. That makes 16. [Typing time note: As I try to explain here what I saw, I write ... "No more that way (hypotenuse on left side). That's 2. Now use the bottom for the hypotenuse. 2 more." And I realize I'm only getting 8 this way. I search and search for more, and don't find them. I think I made a mistake on BART. I'll keep typing up my original work, though.]

So 4 triangles gives 16. That's it. 3x16=48, 3x2^4. This was 2x2 (of squares), so perhaps we'll have 3xn^4. Try a 3x3 (of squares) picture. I start drawing it. Uh oh. I see something bigger in the first one. Half the big square, duh. [Although I say 'duh' to myself, I don't feel bad. In fact I feel good. I know that it only feels dumb after I see something new.] 4 of those... Now I have 52. No sense trying to find a pattern yet.

I finish drawing 3x3. I'm looking for a way to classify the different triangles, so I'm redrawing one of each size, trying to see how they relate. I see that sometimes the hypotenuse is vertical or horizontal, and sometimes it's diagonal. Hmm, I also want to write each size as a multiplication, since I think that might help me see patterns. I'm calling the smallest triangles 2x1 (counting the graph paper squares as my units). I see that the smallest have a vertical or horizontal hypotenuse (I'll use VH for these). There are 4 in each square times 3^2 squares = 36. The ones that use 2 little triangles, 2x2 (on the graph paper), have a diagonal hypotenuse (D). There are again 4 in each square times 3^2 squares = 36.

Using 4 little triangles, 4x2, back to VH. With hypotenuse on the left, I see one toward the top, and I can slide down a bit for a second one. I can slide the hypotenuse to the right, to the second or third vertical line. 4 (directions from VH hyp) times 2 times 3 = 24.

Using 8 little triangles, 4x4, back to D. Shorter side on left (top or slid down) or slid to the right one box (top or slid down), gives 4 times 4 directions (legs on left and bottom, bottom and right, right and top, top and left), or 4*2*2 = 16.

16 little triangles, 6x3, back to VH. Hypotenuse (or spine) at left gives 1 at left and one more (slide right). 4 directions. 4*2*1 = 8. 32 little triangles, 6x6, back to D. There are 4*1^2 = 4. The total for 3x3 (of squares) is 124 triangles.

I'm thinking that the way I label sizes will confuse anyone reading my account, so I decide to change to size labels that are based on the small squares being the unit. So the smallest triangle is 1x 1/2. I change all the sizes for the 3x3 square above. (Biggest becomes 3x3.)

Count for

I guess it's time for 4x4. I draw this one smaller, to fit on what's left of the page. Counting is quicker now.

Oops. I left out the 4x4. There are 4*1^2 of them. The diagonal pattern has held, and I still see no clear pattern on the VH triangles. On to 5x5. I draw it, and I draw a representative triangle of each size. Ride over. Time for the conference...

I have typed up all my notes. Now I need to go back to drawing to finish thinking about the 5x5. I may not have time for that today, so I'm posting, and will edit later.

Here's my thought process:

ReplyDeleteWell, the most straightforward thing to do would be to organized the triangles by size and orientation and then "count" the ones in each class. * For instance, if we take the square to be 4x4, then the smallest triangle has area 1/4 and the largest triangle has area 8. The possible areas are 1/4, 1, 9/4, 4, 1/2, 2, 9/2, and 4. For each size triangle, there are 4 orientations, which yields 64 (1/4), 48 (1), 24 (9/4), 8 (4), 64 (1/2), 36 (2), 16 (9/2), and 4 (4). To count the number of triangles, I looked at how many possible points would work as the right angle vertex and multiplied by 4 for the possible orientations. (This was a bit easier for the second set of triangles, because one can see the pattern of n^2.)

* Before I actually counted, I wondered if there were another way to do this problem. I first thought of counting pairs of points along the various lines, because if you can form a mapping between a given pair of points and the right triangles it can form, that will allow you to count the total number, since each triangle will have three pairs of collinear points. The problem with this is that some pairs of points can be used as both the leg or hypotenuse of a triangle, and other pairs only used as the leg. I don't think this method is completely useless, but it does make the counting more difficult. ^

^ At this point, I thought of trying another way, which was to consider a smaller case of a 1x1 square and trying to extrapolate a pattern. But I ended up starting typing up my thoughts and realized the first way actually wasn't too bad, and ended up following it through to completion. *

+ After typing up the second way, I think it is made easier if we color the points red and black (standard bipartite coloring) where the vertices are red if they are lattice points, and black if they are centers of the 1x1 squares. Then considering a diagonal of the 4x4 square: there are 5 red points, and 4 black points. Hmm, this doesn't seem to be helping. The smaller red-red pairs can be used as either leg or hypotenuse, but the larger ones may only be used as legs. black-black pairs are useless. red-black pairs are only used as legs, but not all pairs are valid either. This seems to devolve into a similar method as the first, so I'm going to give up on it and try method 3. @

@ I don't think the method is all that great, for finding a pattern, but I wonder if the following would work: Consider a simple 4x4 grid. It has no triangles. Then for each diagonal drawn in, we can compute how many triangles are added? Except that some of the triangles depend on both diagonals to be there.

Hao, I'm not reading your comment yet, since I'm not done. I'll definitely come back to it.

ReplyDeleteI believe I have a total for 4x4. But I wanted to say that I'm really looking for nxn, and that's quite a bit more complicated.

I think I miscounted the area 4 triangles anyway. :)

ReplyDeleteThis is what I came up with for n x n:

ReplyDelete[;4\sum_{i=1}^n{\left[\left(n-\left\lfloor\frac{i-1}{2}}\right\rfloor\right)\left(n+1-i\right)+i^2\right]};]

It won't show up properly if you don't have TeX the World (which I heard about from Terence Tao)

deformatted:

4 * sum(i = 1..n) of [(n-floor((i-1)/2))(n+1-i)+i^2]

See Math 2.0 for my answer.

ReplyDelete