Triangles with fixed perimeter

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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