How Many Non-Congruent Triangles with Integer Sides Can a Given Perimeter Form?

[anemone]

Here is this week's POTW:

-----

For any natural number $n$, ($n\ge 3$), let $f(n)$ denote the number of non-congruent integer-sided triangles with perimeter $n$ (e.g., $f(3)=1,\,f(4)=0,\,f(7)=2$). Show that

a. $f(1999)>f(1996)$,
b. $f(2000)=f(1997)$.

-----

 

[anemone]

Congratulations to kaliprasad for his correct solution! (Cool)

You can find the suggested solution as follows:

Spoiler

(a) Let $a,\,b,\,c$ be the sides of a triangle with $a+b+c=1996$ and each being a positive integer. Then $a+1,\,b+1,\,c+1$ are also sides of a triangle with perimeter 1999 because $b+c>a$ implies $(b+1)+(c+1)>a+1$ and so on. Moreover (999,999,1) form the sides of a triangle with perimeter 1999, which is not obtainable in the form $a+1,\,b+1,\,c+1$ where $a,\,b,\,c$ are the integers and the sides of a triangle with $a+b+c=1996$. We conclude that $f(1999)>f(1996)$.

(b) As in the case (a), we conclude that $f(2000)>f(1997)$. On the other hand, if $x,\,y,\,z$ are the integer sides of a triangle with $x+y+z=2000$, and say $x\ge y\ge z\ge 1$, then we cannot have $z=1$ for otherwise we would get $x+y=1999$, forcing $x,\,y$ to have opposite parity so that $x-y\ge 1=z$, violating triangle inequality for $x,\,y,\,z$. Hence $x\ge y \ge z >1$. This implies that $x-1\ge y-1 \ge z-1 >0$. We already have $y+z>x$. If $x\ge y+z-1$, then we see that $y+z-1\le x<y+z$, showing that $y+z-1=x$. Hence, we obtain $2000=x+y+z=2x+1$ which is impossible. We conclude that $x<y+z-1$. This shows that $x-1<(y-1)+(z-1)$ and hence $x-1,\,y-1,\,z-1$ are the sides of a triangle with perimeter 1997. This gives $f(2000)\le f(1997)$. Thus we obtain the desired result.