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.
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.
Posts
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.
ReplyDeleteThe first thought that comes to my mind is that you can significantly reduce the amount of counting you need to do by taking advantage of the symmetry.
ReplyDelete[Yes, I realize this post is over three years old, but I just had to chime in. This may get a bit long-winded, please bear with me. Sorry if this is hard to follow, I'm not very good at explaining things. I'm not 100% sure my process is correct and would love some feedback]
ReplyDeleteI counted 184
64 very small
64 small [made up of 2 very smalls]
24 medium [made up of 4 very smalls]
20 large [made up of 8 very smalls]
8 very large [made up of 16 very smalls]
4 huge [made up of 32 very smalls]
My process:
There are many small triangles (size large and below), so I simplified counting them by splitting the entire square in half diagonally. Then, for counting very smalls, smalls, and mediums, I only examined the left half of that half** [see explanation below for why this is necessary].
Splitting the square in half right diagonally, then looking at the left half of the half on the right, I counted 16 very small triangles. Since there are 4 distinct halves from doing diagonal splits on the square, you multiply 16 by 4 to get the total number of very small triangles, 64.
Now looking at the same half of the half, I counted 12 smalls, plus the 4 across the right side of the left half when you join that half with the other half, so 16. Then multiplying by 4 gives a total of 64 smalls.
For the mediums, I counted 6 per half of half, so 24 total.
I used a different approach for counting the large triangles. Instead of looking at half of a diagonal half, I looked at the entire half after splitting the square diagonally (looking at the whole group of 32 very smalls).
Then for one half I counted the number of large triangles that were facing the same direction or the opposite direction as that half. Doing it this way will ensure that you are only including the large triangles unique to that half. I counted 5 large triangles for that half, so multiplying by 4 gives 20 total.
When it came to counting the very large triangles, it was no longer useful to split up the square, so I viewed it as a whole. There are 4 very large triangles that have hypotenuses across the center of the square (2 vertical, 2 horizontal) and 4 very large triangles, each one having their hypotenuse aligned with a side of the square.
Finally, I counted the huge triangles simply by counting the triangles that result from the 2 ways of splitting the square in half, a total of 4.
**This is done to avoid counting the same triangles twice, as there are 2 ways of splitting the square in half diagonally, left diagonally and right diagonally. Therefore, the entire square could 4 distinct halves, and each half will share the same triangles as the 2 halves from splitting the square in the other way. For instance, if I split the square left diagonally then looked at the half on the right, the left half of that half is the same as the right half of the left half from splitting the square right diagonally. Likewise, the right half of the right half after a left diagonal split on the square is the same as the left half of the right half after a right diagonal split [I view the hypotenuse as the bottom of a triangle]. Notice how when you look at only the right half or only the left half of each half after a left diagonal split or right diagonal split, each of the 4 distinct halves will have a unique set of triangles. So when you count the triangles on just half of a half, you are not counting the same triangles more than once.
Oh dear. I see that I never finished this. Thanks, CMD619, for bringing me back here. Working on it now.
ReplyDeleteCMD619, I get 268, but I still haven't solved for a rectangle of size nxn.
ReplyDeleteI don't see enough different sizes in your list. You left out the 9s and 18s.
I just double-checked my 268. Hao, is that what you get? I get 492 for the 5x5 rectangle. And I'm working on the nxn...
ReplyDeleteEvens and odds work a bit differently, but if I take a hint from Hao's floor, and use ceiling, which fits my thinking better, I get 4*sum(i=1 to n) of [(n+1-i)(2n+2-i-ceiling(i/2))]. That's the simplified form. It's easier to see the meaning before you algebraically simplify.
The triangles that have a diagonal hypotenuse are easier to describe in terms of n. They point 4 directions, so it's 4 times something. The number you find depends on the size, and you'll get (n+1-i)^2 of these in each direction, so 4*(n+1-i)^2, for i going from 1 to n.
Now for the triangles with a vertical or horizontal hypotenuse. Using hypotenuse on the bottom to think (knowing there will be 4 directions), we see the smallest ones go up 1/2 of a rectangle, the next size (which are 4 triangles) go up a whole rectangle, the next size (9 triangles) go up 1 1/2 rectangles. When we count how many of these across and how many rows going up, we need to round up those fractions. That's why I use ceiling. So for these I get 4*(n+1-i)(n+1-ceiling(i/2)).
Adding the two parts together, we get 4*(n+1-i)^2 + 4*(n+1-i)(n+1-ceiling(i/2)), which simplifies to 4*(n+1-i)[2n+2-i-ceiling(i/2)].
I spent a very long time on this three years ago, and left it entirely until now. I am amazed that my brain held onto whatever it learned doing this, and I was able to solve it completely in an hour and a half just now. Very interesting. (I think of myself as having a very bad memory, but the part of my memory that holds the thinking process for this works just fine!)
I finally went and checked Dave Richeson's solution. He approaches it quite a bit differently. I checked my answer against his, saw I had a mistake in the formula and fixed it. He simplifies further, since summations can always be re-written as formulas without summation. He also finds the sequence of numbers we get, 8,44,124,268,492,... for rectangles of side length 1,2,3,... in the On-line Encyclopedia of Integer Sequences. Very cool!
Wow, I'm surprised at the quick response. You're right, there are size 18s! How did I miss those? I was convinced that the different sizes of the triangles were all powers of 2. I counted 4 18s, bringing my total to 188. I don't see any size 9s, where are you seeing them? I don't think you can have triangles larger than very small that are made up of an odd number of very small triangles.
ReplyDeleteI knew there must be someway to come up with a formula for finding the total number of triangles, but I didn't even know how to start on that. Right now I'm trying to understand yours, but I'm not sure what you mean by ceiling.
ReplyDeleteOh, I finally see the size 9s. Damn, this is going to be even harder than I thought.
ReplyDelete>Wow, I'm surprised at the quick response.
ReplyDeleteAhh, the miracles of modern technology.
>I'm not sure what you mean by ceiling.
It means, if your number isn't a whole number, round up to the whole number above.
>this is going to be even harder than I thought.
Sleep on it a few times. You'll get it.
So here's my revised count:
ReplyDelete256 total
64 size 1s
64 size 2s
48 size 4s
36 size 8s
24 size 9s
8 size 16s
8 size 18s
4 size 32s
which 12 am I missing?
I think you missed some 16s and 18s.
ReplyDeleteI just saw that there are three 16s facing each direction, so 12 total. But I'm still only seeing two 18s facing each corner. Now I've found 260 triangles.
ReplyDeleteSorry, I threw out my notes when I was cleaning up last night. My recommendation is that you outline one and slowly shift it left or right up or down.
ReplyDeleteThat's what I've been doing after realizing how flawed my original approach was.
ReplyDeletePerhaps not as flawed as you're thinking. Each time we approach a problem a new way, or another time, it adds to what we've done before. Think of your "flawed" approach as getting to know the problem.
ReplyDeleteI just entered the summation form of the formula given on On-line Encyclopedia of Integer Sequences into my calculator (TI-84 plus) for a 4x4, and I got 280, the same answer posted by Cooper Macbeh in the Math 2.0 discussion. But when I enter the closed form I get 268. Why's that?
ReplyDeleteWhat did you do with their round(i/2)? They meant the same thing I did with ceiling(i/2), though it's not as obvious with the term round what should happen when you're halfway between two numbers. Unfortunately, I no longer have a TI-84. Perhaps it doesn't do round(i/2) the way the OEIS meant it. (I tried to google it, and couldn't figure it out for sure.) If you use int(i/2+.5), I think you'll get ceiling. int() is the equivalent of floor. (They may act differently on negatives, but that probably depends on what device you're using.)
ReplyDeleteYep, it was the rounding. I just entered it as i/2. I didn't understand how to use the round function on the calculator, so I just set it up so that everything gets rounded to the closest integer. From the mode menu I changed the rounding from float to 0. After testing out the rounding, I learned that rational numbers with 5 at the end of the decimal portion are rounded up. So i/2 was still rounded to the next highest integer, but it may not have been the only thing that was rounded. I now understand how to use the round function: first operand is number to be rounded: second operand is number of decimal places. So I set the global rounding setting back to float and replaced i/2 with round(i/2), giving me the result 268. I'm still interested in seeing if I can find the last 8 triangles from examining the 4x4. As far as I know, there is no proof of the formula.
ReplyDeleteThe math-future (or math 2.0) discussion is here: https://groups.google.com/forum/#!topic/mathfuture/W41lMxjhQ1U
ReplyDeleteHmm, I didn't write my process out as a proof, but I feel like I have proved it.
ReplyDeleteYes, I suppose explaining how you made your formula does serve as a proof.
ReplyDeleteOk, I finally found 3 18s facing each direction, bringing my total to 264. Counting all of the triangles in 1x1, 2x2, and 3x3 squares helped me find triangles in the 4x4 I previously missed.
ReplyDeleteMy revised count:
64 size 1s
64 size 2s
48 size 4s
36 size 8s
24 size 9s
12 size 16s
12 size 18s
4 size 32s
Only 4 more to find!
I finally found the last 4. There were 4 18s I missed. I found one by starting in the top left corner of the 4x4, shifting left 1 square, then shifting down 1 square. I forgot to check for this size triangle closer to the center of the 4x4. Also, I didn't think there would be more 18s than 16s since 18s are larger.
ReplyDeleteMy final count:
64 size 1s
64 size 2s
48 size 4s
36 size 8s
24 size 9s
12 size 16s
16 size 18s
4 size 32s
268 total.
That did seem odd, didn't it? (More 18s than 16s.)
ReplyDelete"I found one by starting in the top left corner of the 4x4"
ReplyDeleteI meant top right corner.
"That did seem odd, didn't it? (More 18s than 16s.)"
Yes, I wasn't expecting that, which is why I was mostly focusing on finding more triangles smaller than 18.
so what is the correct answer?
ReplyDeleteLeanne, I'm not sure what you're asking. There are 268 triangles in that 4x4 picture in the post. To find them takes a lot of work, and it's a lot more interesting if you're trying to find patterns, and understand them.
ReplyDeleteI'm currently taking a course on programming algorithms at SDSU and it is by far the most math-intensive computer science course there is. I think it'd be very useful to learn how to come up with a formula for a problem like you have. It seems like an essential skill for writing programs designed to calculate an answer for a problem.
ReplyDelete