Sunday, August 2, 2009

How Many Triangles?

In a previous post, How many squares are there on a chess board?, I closed with the following challenge:

How many triangles (of all sizes) do you see in the equilateral triangle below?

A lot of people attempted a solution, and a few got it right, but this puzzle proved a bit more challenging than counting the squares on a chessboard so it's time to give the full solution. It might seem like a simple task of counting up the triangles, but it's even harder to keep track of which triangles you've already counted than it was with squares. In addition to that, I'm always much more interested in a general approach to a puzzle than I am in the solution to a specific instance of the puzzle.

Before we begin, let's get a bit of terminology out of the way. I'll be referring to each specific instance of this problem by the number of unit-triangles at its base. The unit-triangle is the smallest triangle in each image, and the base is the number of unit-triangles along the bottom edge. In the image above, there are five unit-triangles in the base. Let's call the number of unit-triangles in an image u(n), where n is the number of unit-triangles in the base, and the total number of triangles in an image T(n).

Starting at the beginning, we see that the simplest case consists of only one triangle.

u(1) = 1
T(1) = 1

Next we have a triangle that has two triangles at its base. Counting the unit-triangles we get four, plus the larger triangle they form, for a total of five.

u(2) = 4
T(2) = 5

Next we move up to a base-3 triangle. You can see from the image below that it's made up of 9 units.

u(3) = 9

In addition, there are three base-2 triangles (one in each corner, see images below), plus the base-3 triangle itself, for a total of 13.

T(3) = 13

At this point you should note that any base-n triangle consists of three base-(n-1) triangles, one for each corner. The only exception to this rule is at base-2, which we saw consists of four base-1 triangles, one for each corner and one in the middle. From here on, I won't illustrate the three corner base-(n-1) triangles.

A triangle with a base of four units consists of itself, 16 units, seven base-2 triangles, and the three base-3 triangles in each corner, for a total of 27.

u(4) = 16
T(4) = 27

I won't illustrate all seven of the base-2 triangles, but many people do miscount them, so I'll list them by their numbered units to help you visualize them.

{ 1, 2, 3, 4 }
{ 2, 5, 6, 7 }
{ 4, 7, 8, 9 }
{ 5, 10, 11, 12 }
{ 7, 12, 13, 14 }
{ 9, 14, 15, 16 }
{ 6, 7, 8, 13 }

Note that the last triangle listed, { 6, 7, 8, 13 }, is a downward-pointing triangle. This is important because there are more of these as you increase the size of the base, and because many people overlook them while counting. Make sure that you can see all the triangles listed before continuing on.

Finally, we come to the base-5 triangle that we set out to solve at the beginning. It's made up of 25 units, 13 base-2 triangles, six base-3 triangles, three base-4 triangles in the corners, and itself for a total of 48 triangles.

u(5) = 25
T(5) = 48

I won't go through and illustrate all 48 of them, but hopefully the visual cues I provided in the previous illustrations help you to arrive at the same count that I did.

A General Formula

Now that we have the solutions to several small instances of the triangle problem, we have enough information to search for a general formula. Other than the fact that for each instance the number of unit-triangles is the square of the base, I don't see any interesting patterns in the sequence, so I'll skip directly to searching for one. Searching for the sequence 1, 5, 13, 27, 48 in the Online Encyclopedia of Integer Sequences leads me to this resource.

The comments identify this problem as
Number of triangles in triangular matchstick arrangement of side n.
which is a very general way of stating the original problem (where the problem was originally posed by laying out matchsticks on a table, rather than drawing triangles in an image editor).

The formula given for the sequence is:

T(n) = floor(n * (n + 2) * (2n + 1) / 8)

I could stop there, but I want to explain what the floor function is, and why it's needed in this case. The floor function in mathematics simply gives the largest integer less than or equal to its input. It simply rounds down to the nearest whole number (unless the input is already a whole number, in which case the output is exactly the same whole number as the input).

To see why we need to floor the results of this calculation, consider two things. First, when we're counting the triangles in the original image, I hope it's apparent that we will always come up with a whole number of triangles. That is, we'll never have some fractional part of a triangle left over. The answer will always be an integer value. Second, if we look at the results of the formula without using the floor function, we can see that it is needed.

f(n) = n * (n + 2) * (2n + 1) / 8
f(1) = 1 * (1 + 2) * (2*1 + 1) / 8 = 1.125
f(2) = 2 * (2 + 2) * (2*2 + 1) / 8 = 5.000
f(3) = 3 * (3 + 2) * (2*3 + 1) / 8 = 13.125
f(4) = 4 * (4 + 2) * (2*4 + 1) / 8 = 27.000
f(5) = 5 * (5 + 2) * (2*5 + 1) / 8 = 48.125

Note that when n is odd, there is always some a fractional remainder left over from applying the formula. Flooring the result removes this residue, giving us the same whole number answer we would arrive at by counting.

Since the remainder is always exactly equal to 1/8, we could get the same result by using two different formulas, one for even inputs, and one for odd inputs. This is the approach taken with the formulas given on on Wolfram MathWorld's Triangle Tiling article.


In Closing...

Congratulations to everyone who took the time to work through the solution to this problem. I'd like to thank everyone who left a comment on the original post. Your questions and comments made that one of the most fun (for me) posts I've written so far. I hope you enjoyed it as much as I did.

44 comments:

Sam152 said...

Epic post as usual.

Evgeni said...

It'd be an interesting exercise to write a program that counts triangles. Counting base-1 and base-2 is simple. Starting from base-3 things get hairy. The challenge is to come up with the efficient data structure that unrolls the biggest triangle into smaller ones.

Bill the Lizard said...

Evgeni,
My immediate thought was some kind of tree, but there's so much overlap that I don't know right off how to make it efficient.

That would definitely be an interesting exercise. You could make it a full-blown project if you include an image capturing feature like Sudoku Magic.

Anonymous said...

I wrote a program in Python that calculates the number of triangles in one of these puzzles with just the number of base triangles (unit ones). But I used a completely different approach/formula. I felt very sad when I found out about this equation because I hoped I was the first person to find a solution. It seems that almost anything that's important or interesting has already been discovered *sigh*.

Bill the Lizard said...

Anon,
Don't be discouraged. It's a good sign if you can come up with that formula on your own, even if you weren't the first. Keep exploring new problems and eventually you'll be the first to solve one.

Anonymous said...

I count this in simple way.
its always 3 * n^2 + 2
where n is number of horizontal lines inside main outer triangle.

Bill the Lizard said...

Anon,
Did you make a mistake typing in the function you're using? The function you posted in your comment gives the sequence

2, 5, 14, 29, 50, 77, 110, 149, ...

which is only correct for one term. It's close for several terms, which is what leads me to believe you made a simple error, but I can't figure out what it is.

Tushar said...

Though this formula of floor{n*(n+2)*(2n+1)/8} does the job, I haven't been able to fully satisfy myself of the derivation of the above result, nor have I been able to find any conclusive proof. I myself have tried to derive it, but have failed leaving me frustrated, any sort of explanation will be helpful

Jeez said...

hi. The derivation is pretty simple, i think. i'm working towards getting the expression/formula to get it for any given level n. Its mostly nested summations, which can be simplified to polynomial expressions, which i'm hoping will work out to the given expression!

my approach [in progress]:
k=0
for b from 1 to n-1:
for a from 1 to b:
k+=a

this gives the count of all upright triangles in the system. its a simple summation formula, but can't write it here, so using pseudocode notation!

any help would be appreciated :)

dualbus said...

Hi, I found your blog because I also became interested in this problem. The solution I found was:
 
              3n - p(n)
f(n) =   ----------------
                   2
 
             3(n-1)^2 + 2(n-1) - p(n-1)
        + ----------------------------------------
                              4
 
           __n-1_
           \               3(i)2 + 2(i) - p(i)
        +     >         ----------------------
           /_____                4
             i = 1
 
 Where p(n) = n (mod 2) **** n even, p(n) = 0; n odd, p(n) = 1
 
Python Implementation
————————————
def p(n):
    return n%2
 
def f(n):
    sum = 0
    for i in range(1,n):
        sum += (3*(i)**2 + 2*(i) - p(i))//4
    return (3*n-p(n))//2 + (3*(n-1)**2 +2*(n-1) - p(n-1))//4 + sum
 
for i in range(10):
    print("A triangle of index " + str(i) + " has " + str(f(i)) + " inscribed triangles.")

dualbus said...

Oh, yeah, the program returns the following:

IDLE 2.6.4 ==== No Subprocess ====
>>>
A triangle of index 0 has 0 inscribed triangles.
A triangle of index 1 has 1 inscribed triangles.
A triangle of index 2 has 5 inscribed triangles.
A triangle of index 3 has 13 inscribed triangles.
A triangle of index 4 has 27 inscribed triangles.
A triangle of index 5 has 48 inscribed triangles.
A triangle of index 6 has 78 inscribed triangles.
A triangle of index 7 has 118 inscribed triangles.
A triangle of index 8 has 170 inscribed triangles.
A triangle of index 9 has 235 inscribed triangles.
>>>



p(n) is the remainder for the division n/2

Bill the Lizard said...

dualbus,
Excellent solution! Thanks for sharing it, and for providing the source code.

Anonymous said...

On the 4 base triangle, I continually come up with 31 triangles. Additional ones not listed are - the entire outline = 1
(1,2,3,4,5,6,7,8,9)= 2
(2,5,6,7,10,11,12,13,14)=3
(4,7,8,9,12,13,14,15,16)= 4
These in addition to the 27 listed equals 31 triangles for a 4 base grid.

Bill the Lizard said...

Anonymous,
Those four are already included in the total count of 27.

"A triangle with a base of four units consists of itself, 16 units, seven base-2 triangles, and the three base-3 triangles in each corner, for a total of 27."

The ones you listed are what I'm calling "itself" (the entire base-4 triangle), and the "the three base-3 triangles in each corner." To illustrate that last part, what you listed as (1,2,3,4,5,6,7,8,9), I would call the base-3 triangle in the top corner.

I hope that helps.

love+idleness said...

Great Post!

What I tried was counting the triangles in each of the base n-1 triangles that use one of the vertices of the base n triangle.

If you do that you've double counted all the triangles in the three base n-2 triangles where the three n-1 triangles overlap.

I can subtract those but would need to add T(n-3) back to count where all three overlap.

Adding one for the big triangle:
3T(n-1) - 3T(n-2) + T(n-3) + 1

Plugging in 0 for T(x) when n-1, n-2, or n-3 are less than 1 makes this work for odd n, but it needs another +1 for even n. This makes sense, since whenever I tried counting this way with even n there was an always an upside down triangle that wasn't counted.

I imagine solving this recurrence gives the equation you posted, but I don't know how to do that.

Anonymous said...

So what am missing why does Engeni want to us base-n(ything). I see a polynomial, my calculus is a bit rustty, but, from memory:

n * (n + 2) * (2n + 1) / 8
is the same as

n * (2n^2 + 4n + n + 2)/8
or
n * (2n^2 + 5n + 2 ) / 8
or
(2n^3 + 5n^2 + 2n) / 8

flame me if I am wrong, I would deserve it.

As for the floor function, computers always round down when converting from float to int, hence if the calculation is done as a float and converted to an int the correct result will be reached.

based on my old maths and in c:

#include
#include


int triangles (int base_triangles)
{
float res;
float n = base_triangles;

res = ((2 * pow(n, 3)) + (5 * pow(n, 2)) + (2 * n)) / 8;

return (int) res;

}

int main (void) {

int i;

for (i = 0; i < 7; i++)
printf("base_triangles = %d, total_triangles = %d\n", i, triangles(i));

}

It seems my calculus is not as rusty as I thought - increase 7 to what you like.

Anonymous said...

Nasty response thingy stole some of my text you will need to include stdio.h (for printf) and stdlib.h (for pow).

T compile I used cygwin - its free and the command:

gcc -o triangles triangles.c

and to run

triangles.exe

Enojy, hopefully someone will learn something.

Prasoon said...

This is awesome. :)

Anonymous said...

Funny, I started out wanting to take a 5x5x5 Rubik's cube apart and ended up here! Amazing. My initial guess, before I went online, to the number of "parts" inside the cube was 248. I have yet to take it apart. Wish me luck.

Anonymous said...

Excel cell formula: =POWER(A1,3)/4+POWER(A1,2)*5/8+A1/4+(POWER(-1,A1)-1)/16
where you pop the length of the side in cell A1.

k vishwanath reddy said...

good one...

Anonymous said...

#include
#include
#include
int main(void)
{
int T,i,j;
long long int N,sum=0,num1,num2;
scanf("%d",&T);
if(T>10000)
{
exit(0);
}
while(T--)
{
scanf("%lld",&N);
sum=0;
if(N<1||N>1000000)
{
exit(0);
}
sum+=(N*N*N+3*N*N+2*N)/6;
sum+=((N*N-N)*((N/2)+1))/2;
sum+=((-2*N+1)*((N/2)*((N/2)+1)))/2;
sum+=(4*((N/2)*((N/2)+1)*(2*(N/2)+1))/6)/2;
printf("%lld\n",sum);
}
return 0;
}

Anonymous said...

and the messages continue flowing into my mobile, like today I got 2 again.From hundreds of pages similar to yours, somebody chose exactly yours to link with and stealing money.He can be one of your 'bloggers' and he made a small revealing mistake-in one of his messages he used 'ae' instead of Finnish letter'a' with two dots above, thus providing his comp. wasn't bought in Finland(where computers are relatively cheap).Using deduction, I've found a few more things about this guy.Maybe URL is public, but many other things connected with this person are unique, like a psychological portrait.Anyway,he's keeping spoiling your good reputation and I'm changing my prepaid card, so he can send messages-it's idle.

Amit Singh said...

Do I need to say that you are awesome while explaining things, Thanks a TON !!!

Anonymous said...

Hello...im a college prep student, just started on the 2 of july. anyway our math teacher gave us this problem as homework to try to find patterns. anyway i've found an alternate yet longer way to figure out how many triangles are in the triangle. now im not good at mathematical formulae, but i'll explain it the best i can.

since the number of unit triangles in the larger trangle is always the number or rows times itself(i.e. row 8 has 64 unit triangles, 8*8=64) if you take the number of unit triangles and subtract the row minus 1 you'll get the number of base 2 triangles in the next row. it goes on and on, until the number stagnates and will always be that number in that diagonal row. since i probably lost most of you here's a sort of graph:

BT= Base triangles

row#|BT1|BT2|BT3|BT4|BT5|BT6|BT7
1 | 1 | | | | | |
2 | 4 | 1 | | | | |
3 | 9 | 3 | 1 | | | |
4 | 16| 7 | 3 | 1 | | |
5 | 25| 13| 6 | 3 | 1 | |
6 | 36| 21| 11| 6 | 3 | 1 |
7 | 49| 31| 18| 10| 6 | 3 | 1



as you can see, the number of triangles starts to diminish and finally stagnate as you go down diagonally. i've used my formula to get the number of triangles in a 20 row triangle. yes...it was very daunting...but it wasnt nearly as painful as counting the first ten rows and recording my findings by hand...anyways thanks for listening to a kid like me. if you find anything else out about this please post it.

Anonymous said...

ugh...srry that graph didnt come out like i wanted this should be better:
BT= Base triangles

row#|BT1|BT2|BT3|BT4|BT5|BT6|BT7
1---|-1-|---|---|---|---|---|---
2---|-4-|-1-|---|---|---|---|---
3---|-9-|-3-|-1-|---|---|---|---
4---|-16|-7-|-3-|-1-|---|---|---
5---|-25|-13|-6-|-3-|-1-|---|---
6---|-36|-21|-11|-6-|-3-|-1-|---
7---|-49|-31|-18|-10|-6-|-3-|-1-

Anonymous said...

i give up XD frakin hate computers somtimes...

fcexpress80 said...

Base 1 = 1
Base 2 = 1 + 4
Base 3 = 1 + 3 + 9
Base 4 = 1 + 3 + 7 +16
Base 5 = 1 + 3 + 6 +13+25

We could now assume that for a Base 6 triangle, the answer will be in the form of: 1 + 3 + ... +36. But how would one find the three numbers in between?

We should notice that the second number in the solutions, for Base 3 and greater is always going to be "3".

We also notice that the third number in the Base 4 sequence is 7, 2 less than the third number in the Base 3 sequence. The third number in the Base 5 sequence is 6, which is one less than the third number in the Base 4 sequence. Following the pattern set in the second and third sequence numbers for Base 5 triangles and less, the third number in the sequence will be 6 and remain 6 for all Base n triangles.

To summarize:

The first number when calculating any Base n triangles will be "1".

The second term for Base n sequence (where n is > 2) will be "3".

The third term for Base n sequence (where n is > 4) will always be "6".

The fourth term for Base n sequence (where n > 6) will always be "10".

The xth term for a Base n sequence (where n > 3x-2) will always be a "triangle number", i.e. 1,3,6,10,15,21....

Also, as many have noted, the last term in any Base n sequence will be n^2.

So there is a predictable sequence of terms where one could devise the answer to the "number of triangles" for any Base n without using the admittedly convenient formula and without tedious counting.

fcexpress80 said...

Base 6 : 1 + 3 + 6 +11 +21 +36
Base 7 : 1 + 3 + 6 +10 +18 +31 +49
Base 8 : 1 + 3 + 6 +10 +16 +27 +43 +64
Base 9 : 1 + 3 + 6 +10 +15 +24 +38 +57 + 81
Base10 : 1 + 3 + 6 +10 +15 +22 +34 +51 + 73 +100

Anonymous said...

Thanks for this site!

I solve it by counting the “up-triangles” (those pointing up) first, unit and non-unit.

Up(n) = n(n+1)(n+2)/6

then the down-triangles

Down(n) = n(n+2)(2n-1) – mod(n,2)/8

I saw a pattern then. Putting them together you get your result:

(n(n+2)(2n+1) – mod(n,2))/8

Anonymous said...

Oops

Down(n) = n(n+2)(2n-1)/24 – mod(n,2)/8

Johny said...

Hi this is john.try this [4n^3+10n^2+4n-1+(-1)^n]/16, if you want to know the total number of triangles with ...where is the number of trianles in the bade(BT)=n

Johny said...

Hi this is john.try this [4n^3+10n^2+4n-1+(-1)^n]/16, if you want to know the total number of triangles with ...where is the number of trianles in the bade(BT)=n

Gabriel Rainwater said...

Here's the formula I figured out before I found your site.

sum^b_k{\lfloor \frac{b + k + 1}{\lceil \frac{1}{2} (b + k + 1) \rceil} \rfloor sum^k_i{i}},

where b is the number of unit triangles in the base. Sorry about the messy LaTeX; if you can't read it, here's the mathurl: mathurl.com/8r9vpmj

I really wish distinguishing between odd and even wasn't such a hassle for math notation. Really, all that mess of floor and ceiling in the middle of my formula does is simplify to either 1 or 2, depending on whether b and k are both odd, both even, or one is odd and the other even. It shouldn't be so complicated.

Александър Дудев said...

http://popkasa-rs.com/counttriangles.php

It works with an alghoritm. I also thinked, that I found a solution, before I saw the formula. Lets say that sum(5) = 5+4+3+2+1, and the base is broi1, and broi2 is broi1-1(broi2 actually represent the triangles with the edge poining downside)

$sum = 0;
while ($broi1 > 0)
{
$sum = $sum + sum($broi1);
if ($broi2 > 0)
{
$sum = $sum + makesum($broi2);
}

$broi1--;
$broi2 = $broi2 - 2;
}

And the $sum is the exact count of triangles, which you can find in the picture. :)

gustavo cota said...

I found a formula for this problem: Triangles = (cos(pi*n) + 4n^3 + 10n^2 + 4n -1)/16

Mike said...

The formula you gave us is not so hard to calculate, it's the sum of: (1+2+3+4+...+n) + (1^2+2^2+3^2+...+n^2) +
Now we have the trick, for even:
+[1+3+5+...+(n-1)]+
[1^2+2^2+3^2+...+(n-1)^2]
Or for odd:
+[2+4+6+...+(n-1)] +
+[2^2+4^2+6^2+...+(n-1)^2]
If you want to know how you get to this step, it's simple, calculate first the triangles with the point up and after the ones with the point down.

Mike said...

Sorry, my mistake at something, at even the second sum is : 1^2+3^2+5^2+...+(n-1)^2

Mator said...

Yes, yes. Finding the number of triangles in an equilateral triangle comprised of equilateral triangle units is easy. The huge number of comments preceding mine have provided many formulae to define it.

Let's step it up.

How many triangles are there in a square grid of unknown size?

Link to PhysicsForums Topic

Budi Legowo said...

The floor function is nice!
Formula I came up with before I found this site:
1/4*(n*(n+1)^2 + 2*int(n/2)*int((n+1)/2))

Anonymous said...

Hey all ...
First I started coung the difference of triangles made up of one small triangle and I saw that its the same of a function y =x^2 .. and calculated the difference in triangles of 4 small triangles as every one raw increases the number .... Finally there is a big relation sequenced between these difference . The table is amazing if you need it add me or enter my page Ahmad zeinddein ... physics and mathematics devils https://www.facebook.com/pages/Physics-and-mathematics-devils/735033053173839

Anonymous said...

Thankyou so much this helped me understand this alot more.

Anonymous said...

thanks man....for taking the time and effort

Putri Monalisa said...

It'd be an interesting exercise to write a program that counts triangles. Counting base-1 and base-2 is simple. Starting from base-3 things get hairy. The challenge is to come up with the efficient data structure that unrolls the biggest triangle into smaller ones.
Ide Bisnis Sampingan