1
$\begingroup$

For any given natural number $n$, let $T_n$ be the number of triangles with positive area and three integer side-lengths summing to $n$. For example:

  • $T_5=1$ because the only such triangle with $n=5$ has side-lengths $1,2,2$;
  • $T_6=1$ because the only such triangle with $n=6$ is the equilateral one with side-length $2$;
  • $T_9=3$ because there are three such triangles with $n=9$, namely those with side-lengths $3,3,3$ or $1,4,4$ or $2,3,4$.

What is the smallest $n$ for which $T_n>2016$?

This was adapted from a problem in the Canadian Mathematics Competition 2010.

$\endgroup$
  • $\begingroup$ how does a triangle have a negative area? $\endgroup$ – JonMark Perry Sep 26 '16 at 2:22
  • $\begingroup$ It doesn't, but it might (kinda) have zero area. $\endgroup$ – Gareth McCaughan Sep 26 '16 at 2:22
  • $\begingroup$ If, say, n=5, is $T_n$ meant to be 1 (the only possibility being 1+2+2) or 3 (the possibilities being 1+2+2, 2+1+2, and 2+2+1)? $\endgroup$ – Gareth McCaughan Sep 26 '16 at 2:23
  • $\begingroup$ you mean 'non-degenerate'? $\endgroup$ – JonMark Perry Sep 26 '16 at 2:24
  • $\begingroup$ so, partitions of n into 3 parts such that the sum of the smallest 2 parts is greater than the 3rd $\endgroup$ – JonMark Perry Sep 26 '16 at 2:32
4
$\begingroup$

Counting the number of distinct triangles with perimeter $n$ and integer sides generates what is known as Alcuin's sequence (OEIS A005044).

There is also an explicit formula:

$$T(n)=\left\lfloor\frac{n^2+6}{12}\right\rfloor - \left\lfloor\frac n 4\right\rfloor \left\lfloor\frac{n+2}4\right\rfloor$$

The sequence isn't strictly growing, but it can be shown that $T(n+3)\ge T(n)$ for every $n\ge0$.

This property can be used to show that the smallest value of $n$ for which $T(n)\ge 2016$ is

309, having $T(309)=2028$

because $T(306)=1951\lt 2016$, $T(307)=2002\lt 2016$ and $T(308)=1976\lt 2016$, and there can be no $n$ below 306 with $T(n)\ge2002$.

$\endgroup$
2
$\begingroup$

As pointed out already by @Gareth McCaughan in the comments, the answer depends on how you count the triangles.

Case 1: If two the triangles are differentiated by their side lengths, that is, translation, rotation, AND mirroring of a triangle results in the same, then, unless I am missing something, the number you seek for is

$n=309$

for which

$T_{309}=2028>2016$.

Case 2: If triangles having three distinct side-lengths are differentiated once one is the mirror image of the other (this operation cannot be achieved by simple rotations and translations), then, unless I am missing something, the number you seek for is

$n=225$

for which

$T_{225}=2054>2016$.

Note, however, that

your wording of your problem suggests that the smallest such $n$ is interesting, as for any $N>n$, $T_N>T_n$ will hold too. This is not true, as in Case 1 you have $T_{310}=2002$, and in Case 2 you have $T_{226}=2016$.

What you do is

you check for each number $n$ the number of integer partitions with exactly 3 parts such that the parts satisfy the triangle inequality. This can be easily done by computers. Of course, such a triangle necessarily have positive area (by Heron's formula). The difference between the two cases is that partitions with distinct triplets are "counted twice" in the second case, corresponding to mirroring.

$\endgroup$
  • $\begingroup$ I just edited the question to clarify that Case 1 is what I intended (see also my comments to Gareth). Sorry for the confusion! $\endgroup$ – Rand al'Thor Sep 26 '16 at 14:45
  • $\begingroup$ @randal'thor Well... I am not sure if you have clarified: the question is how many triangles you have once you have three distinct side lengths. It seems that T_5 and T_6 are just too small... $\endgroup$ – Matsmath Sep 26 '16 at 14:46
  • $\begingroup$ What? There's no requirement that side-lengths be distinct: isosceles or equilateral triangles are perfectly fine and contribute to the count. $\endgroup$ – Rand al'Thor Sep 26 '16 at 14:51
  • $\begingroup$ @randal'thor the question is that do you differentiate between a triangle and its mirror image. As long as you consider isosceles or equilateral triangles (as you did for n=5, and n=6) there is no concept of this, as those triangles and their mirror image are the same. However, once you reach n=9, you are facing with the case (a,b,c)=(2,3,4), which could if you wish correspond to two triangles: one and its mirror image. $\endgroup$ – Matsmath Sep 26 '16 at 15:00
  • 1
    $\begingroup$ OK, I see the issue. But 'inverse' congruence is still congruence: reflections and rotations are both planar isometries. Edited again. $\endgroup$ – Rand al'Thor Sep 26 '16 at 15:06
1
$\begingroup$

The question is arguably ambiguous -- do we consider side-length triples (2,3,4) and (2,4,3) to define the same triangle or two different ones? I shall begin with the latter version of the question because it's less fiddly, though I suspect the former is actually intended.

Three numbers are the sides of a triangle with positive area if and only if they

can be written as b+c,c+a,a+b with a,b,c positive.

These are the sides of an integer triangle with positive area if and only if

a,b,c are either all integers or all (odd) half-integers.

Hence $T_n$ equals

the number of triples of positive (a,b,c), either all integers or all halves of odd integers, with 2(a+b+c)=n.

Clearly

when n is even we must have a,b,c all positive integers with a+b+c=n/2; and when n is odd we must have a,b,c all positive integer - 1/2 -- say u-1/2,v-1/2,w-1/2 -- with u+v+w=(n+3)/2.

Now,

the number of ways to write $m$ as the sum of three positive integers equals the number of ways to write $m-3$ as the sum of three non-negative integers, which equals $\binom{m-1}{2}$

and therefore we want the first $n$ for which

either $n$ is even and $\binom{n/2-3}{2}>2016$ or $n$ is odd and $\binom{(n-3)/2}{2}>2016$.

Now, it happens that $2016=\binom{64}{2}$ exactly. So this first happens when

either $n$ is even and $n/2-3>64$, or $n$ is odd and $(n-3)/2>64$, whichever happens first; the former happens first at $n=136$ and the latter at $n=133$

and the answer is

n=133.

If we need to consider triangles the same when they have the same side lengths but in a different order, we now have to separate out the cases where they're all different (we only count 1/6 of these), where two are the same (we only count 1/3 of these), and where all three are equal (we count all of these). Note that

those conditions on the side lengths match exactly with identically-stated conditions on the parameters I've called a,b,c.

I am not going to do this right now because it's nearly 4am local time and I should have been in bed hours ago. Perhaps tomorrow, unless it turns out that the version I dealt with above is what was actually intended in which case I needn't bother.

[EDITED to add: Others have done this case so I won't bother. I'm sure they're right :-).]

$\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.