# Triangles with fixed perimeter

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.

• how does a triangle have a negative area? – JMP Sep 26 '16 at 2:22
• It doesn't, but it might (kinda) have zero area. – Gareth McCaughan Sep 26 '16 at 2:22
• 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)? – Gareth McCaughan Sep 26 '16 at 2:23
• you mean 'non-degenerate'? – JMP Sep 26 '16 at 2:24
• so, partitions of n into 3 parts such that the sum of the smallest 2 parts is greater than the 3rd – JMP Sep 26 '16 at 2:32

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

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.

• I just edited the question to clarify that Case 1 is what I intended (see also my comments to Gareth). Sorry for the confusion! – Rand al'Thor Sep 26 '16 at 14:45
• @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... – Matsmath Sep 26 '16 at 14:46
• What? There's no requirement that side-lengths be distinct: isosceles or equilateral triangles are perfectly fine and contribute to the count. – Rand al'Thor Sep 26 '16 at 14:51
• @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. – Matsmath Sep 26 '16 at 15:00
• OK, I see the issue. But 'inverse' congruence is still congruence: reflections and rotations are both planar isometries. Edited again. – Rand al'Thor Sep 26 '16 at 15:06

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$