3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ my best guess is at least 6. Any 3 numbers of the form n,n+1,n+2 is good for forming a triangle. $\endgroup$ – user45765 Oct 22 '14 at 14:56
  • $\begingroup$ 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? $\endgroup$ – Ross Millikan Oct 22 '14 at 15:03
  • $\begingroup$ I cannot get more than 4, and for 4 only 9 sticks are enough. $\endgroup$ – Emanuele Paolini Oct 22 '14 at 15:08
  • $\begingroup$ Can triangles overlap each other? Do the intersections of sticks count as vertices? $\endgroup$ – Emanuele Paolini Oct 22 '14 at 15:12
  • 1
    $\begingroup$ @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$. $\endgroup$ – MJD Nov 4 '16 at 10:47
1
$\begingroup$

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$

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

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.