# There are 10 sticks of length 1,..,10. How many triangles can be formed

There are 10 distinct sticks of length 1,..,10. How many triangles can be formed? I do not know whether there are some counting tricks for this one.

• my best guess is at least 6. Any 3 numbers of the form n,n+1,n+2 is good for forming a triangle. – user45765 Oct 22 '14 at 14:56
• Are you picking exactly three sticks and asking if they can form a triangle, or do you allow a $4,4,5$ triangle with one of the $4$ sides formed by $1+3$ in a straight line? – Ross Millikan Oct 22 '14 at 15:03
• I cannot get more than 4, and for 4 only 9 sticks are enough. – Emanuele Paolini Oct 22 '14 at 15:08
• Can triangles overlap each other? Do the intersections of sticks count as vertices? – Emanuele Paolini Oct 22 '14 at 15:12
• @emanuele I think the triangles are to be formed one at a time. That is, I think the question is how many sets $\{a,b,c\} \subseteq \{1,…,10\}$ satisfy all of $a+b>c$, $b+c>a$, and $c+a>b$. – MJD Nov 4 '16 at 10:47

A first approach is to calculate small values and check OEIS. Assuming you are asking the number of selections without replacement of three sticks that make a nondegenerate triangle I get $1,3,7,7,13,22\dots$ It is easiest to start from $n=4$, for which there is only one triangle. Then for $n=5$ you just need to count the triangles that include $5$, and so on. Putting that into OEIS finds A002623, which the first comment says it is just what you are after. For $n=10$, there are $50$. In the formula section we see $a(n) = \sum_{k=0}^n (-1)^{n-k}{k+3\choose 3}$ and $a(n) = \sum_{k=0}^n \lfloor(k+2)^2/4\rfloor$

• OEIS is fine, but seems a bit like a cop out. How do you compute an answer for any given $n$? – Wildcard Sep 20 '17 at 14:06

given the triangle inequality and a hint of euclidean geometry, a triangle(possibly degenerate) can have sides $a,b,c$ with $a\leq b\leq c$ if and only if $c< a+b$

There are $\binom{10}{3}$ ways to select three integers between $1$ and $10$

It should be clear there are $k-1$ ways to write the number $k$ as a sum of two different positive numbers

Lets count how many of these selections leave the larger number bigger than the sum of the other two classifying on the larger number $c$

$c=4: (4-1)=3$

$c=5:4+3$

$c=6:5+4+3$

In general the number of selections of number that cannot form a triangle where $c$ is the larger number is $3+4+\dots+(c-1)$ This sum is $\frac{(c+2)(c-3)}{2}=\frac{c^2-c-6}{2}$

what we would like is $\sum_{4}^{n}\frac{c^2-c-6}{2}=\frac{1}{2}(\sum_4^nc^2-\sum_n^4c-6(n-3))$

We shall simpify this formula using the formulas for the sum of squares and the gaussian sum to get:

$\frac{1}{2}[(\frac{n(n+1)(2n+1)}{6}-14)-(\frac{n(n+1)}{2}-6)-6(n-3)]$

This can be further simplified by the reader.

All you have to do is change $n$ for $10$ and you should hopefully get the number of triangles up to congruence that can be created using those sticks (some will be degenerate though).