How Many Triangles?

[bizarro]

Recently I saw an ad for an online IQ test. They posed a question on the ad that showed equilateral triangles stacked together to form a bigger equilateral triangle.

Example: http://www.transum.org/Software/SW/Starter_of_the_day/starter_September23.asp

Anyway, I was wondering if anyone can figure out a recurrence relation to solve the problem for any sized triangle (by size I mean the number of individual triangles that make up the length of a side of the "total" triangle, so for example in the link I provided the size would be 4).

I'm curious because I'm currently taking a class on combinatorics, but am unable to apply the theories of combinatorics to solve this particular problem.

[BillGatesJR]

I'm going to go out on a limb here. This has nothing to do with combinatorics however.

First I counted all of the small triangles in the diagram, so 16 miniature triangles to start with. Basically I tried an algebraic method where I took the prime factorization of this number 16, giving me

16 = 2,2,2,2

After this I tried as many things as I could with these twos to see if there was a mathematical way to figure out the actual number of triangles. With the list of twos, any combination will return the original result of sixteen so;

2,2,2,2

8*2=16 or (2*2)(2*2)=16, etc.

After finding out on the website that there are 27 triangles, now I am trying to figure out how to use the number of miniature triangles to determine the number all the triangles present in the diagram. This is where I got stuck.

I tried adding all of the twos from the factor list together to get 8 and add it to 16 to get 24, but I'm still 3 triangles shy...

Perhaps: if x is the number of all the miniature triangles, and n is the number of prime factors x has,

x+n(nth root of x)+3 = number of all triangles? Try it out on other triangle puzzles.

[bizarro]

Hey, I've found the answer with a little help from someone else.

The trick is to divide the problem into two. In one, we count the number of upright triangles, and the other, we count the number of upside-down triangles.

Then, after we figure it out for both upright and upside-down triangles, we add them both together to get the total number of triangles.

Here we go...

----------------------

Let n be the "size" of the total triangle, or diagram (size is measured by the number of individual triangles on the length, so that the example I posted would have size n=4).

Let A_n be the total number of upright triangles within a diagram of size n.

Likewise, B_n will denote the total number of upside-down triangles in a diagram of size n.

Finally, let C_n be the total number of triangles (upright and upside-down) in a diagram of size n. We can see that C_n = A_n + B_n.

First, let's focus on how to count the number of upright triangles:

1) When n=1, A_1=1 (obvious).

2) How many upright-triangles when n=2? By counting, we see there are 3 upright unit-triangles, 1 upside-down unit-triangle (not counted), and 1 larger triangle of "size 2". So by adding 1 to the size of the diagram, we have added 3 additional upright triangles: 2 more unit-triangles, and 1 additional large triangle.

3) What about when n=3? There are now 6 upright-unit triangles, (3 upside-downs which we won't count), 3 larger triangles composed of 4 unit-triangles, and 1 even larger triangle of size 3. So, by adding 1 to the size of the diagram, we have added 6 additional upright triangles: 3 more unit-triangles, 2 more larger triangles (of size 2 each), and 1 additional large triangle of size 3.

By now, we see a pattern forming. Every time we add a size to the triangle (so that total size is n), we add an additional n unit-triangles, another n-1 triangles of size 2, another n-2 triangles of size 3, and so on until we reach an additional 1 triangle of size n (which is largest triangle possible of that size).

Thus, the recurrence relation would be:

A_n = A_n-1 + (summation from 1 to n) k
Initial values: A_1 = 1

where A_n-1 counts the total number of upright triangles before adding an additional size, and (summation from 1 to n) k counts the additional number of upright triangles created by adding a size to the diagram.


Now let's count the number of upside-down triangles.

1) When n=1, there are no upside-down triangles, so B_1 = 0.

2) When n=2, there is 1 upside-down triangle: B_2 = 1.

3) When n=3, there are 3 total upside-down triangles, so B_3 = 3.

4) Now, when n=4, we see that we can count a new upside-down triangle of size 2. So now there are 6 upside-down unit triangles, and 1 upside-down triangle of size 2.

We can begin to see that in order to create a bigger sized upside-down triangle, the diagram must be large enough to contain it. For size 2, we need the total diagram size to be 4, and for size 3, we need the total size to be size 6.

Also, by adding an additional size to the diagram, we will produce an additional n-1 unit-triangles, and an additional n/2 triangles of the next size. And each time the total size of the diagram is an even size, we create 1 additional triangle of size n/2.

Thus, the recurrence relation would be:

B_n = B_n-1 + (summation from 1 to no greater than n/2) n-2k+1
Initial values: B_1 = 0, B_2 = 1


Finally, for the total number of triangles:

C_n = A_n + B_n

As a test, I've used this formula to count the triangles all the way to size 8.

A_n for n = 1,2,3,4,5,6,7,8
n=1: 1
n=2: 4
n=3: 10
n=4: 20
n=5: 35
n=6: 56
n=7: 84
n=8: 120

B_n for n = 1,2,3,4,5,6,7,8
n=1: 0
n=2: 1
n=3: 3
n=4: 7
n=5: 13
n=6: 22
n=7: 34
n=8: 50

C_n for n = 1,2,3,4,5,6,7,8 (using A_n + B_n)
n=1: 1 + 0 = 1
n=2: 4 + 1 = 5
n=3: 10 + 3 = 13
n=4: 20 + 7 = 27
n=5: 35 + 13= 48
n=6: 56 + 22= 78
n=7: 84 + 34= 118
n=8: 120+ 50= 170