2005 Indonesia MO Problems/Problem 1

Problem

Let $n$ be a positive integer. Determine the number of triangles (non congruent) with integral side lengths and the longest side length is $n$.

Solution

WLOG, let $n \ge y \ge x$. The original problem is essentially asking for the number of lattice points that lie within this bound as well as $x + y > n$.

By experimenting with smaller graphs, we can split into two cases.

Case 1: $n$ is even

Below is the case where $n = 4$.

[asy]  import graph; size(8.22 cm); real lsf=0.5; pen dps=linewidth(0.7)+fontsize(10); defaultpen(dps); pen ds=black; real xmin=-1.2,xmax=5.2,ymin=-1.2,ymax=5.2;  pen cqcqcq=rgb(0.75,0.75,0.75), evevff=rgb(0.9,0.9,1), zzttqq=rgb(0.6,0.2,0);   /*grid*/ pen gs=linewidth(0.7)+cqcqcq+linetype("2 2"); real gx=1,gy=1; for(real i=ceil(xmin/gx)*gx;i<=floor(xmax/gx)*gx;i+=gx) draw((i,ymin)--(i,ymax),gs); for(real i=ceil(ymin/gy)*gy;i<=floor(ymax/gy)*gy;i+=gy) draw((xmin,i)--(xmax,i),gs);  Label laxis; laxis.p=fontsize(10);  xaxis(xmin,xmax,defaultpen+black,Ticks(laxis,Step=1.0,Size=2,NoZero),Arrows(6),above=true); yaxis(ymin,ymax,defaultpen+black,Ticks(laxis,Step=1.0,Size=2,NoZero),Arrows(6),above=true); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);  draw((-1,5)--(5,-1),dotted,Arrows); draw((-1,-1)--(5,5),Arrows); draw((4,5)--(4,-1),Arrows); draw((5,4)--(-1,4),Arrows);  [/asy]

The line $x+y>n$ and $y \ge x$ intersect at $(\frac{n}{2},\frac{n}{2})$. By symmetry, for each of the four line segments from the diagonal, there are $\frac{n}{2}$ lattice points. Since there are a total of $(n+1)^2$ lattice points within $0 \le x,y \le n$, by symmetry, each section formed from the diagonals has $\frac{(n+1)^2 - 2n - 1}{4} = \frac{n^2}{4}$ lattice points. We want the points on lines $y = n$, $y = x$ and not $x+y=n$, so there are $\frac{n^2 + 2n}{4}$ points that satisfy the conditions if $n$ is even.

Case 1: $n$ is odd

Below is the case where $n = 5$.

[asy]  import graph; size(8.22 cm); real lsf=0.5; pen dps=linewidth(0.7)+fontsize(10); defaultpen(dps); pen ds=black; real xmin=-1.2,xmax=6.2,ymin=-1.2,ymax=6.2;  pen cqcqcq=rgb(0.75,0.75,0.75), evevff=rgb(0.9,0.9,1), zzttqq=rgb(0.6,0.2,0);   /*grid*/ pen gs=linewidth(0.7)+cqcqcq+linetype("2 2"); real gx=1,gy=1; for(real i=ceil(xmin/gx)*gx;i<=floor(xmax/gx)*gx;i+=gx) draw((i,ymin)--(i,ymax),gs); for(real i=ceil(ymin/gy)*gy;i<=floor(ymax/gy)*gy;i+=gy) draw((xmin,i)--(xmax,i),gs);  Label laxis; laxis.p=fontsize(10);  xaxis(xmin,xmax,defaultpen+black,Ticks(laxis,Step=1.0,Size=2,NoZero),Arrows(6),above=true); yaxis(ymin,ymax,defaultpen+black,Ticks(laxis,Step=1.0,Size=2,NoZero),Arrows(6),above=true); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);  draw((-1,6)--(6,-1),dotted,Arrows); draw((-1,-1)--(6,6),Arrows); draw((5,6)--(5,-1),Arrows); draw((6,5)--(-1,5),Arrows);  [/asy]

The line $x+y>n$ and $y \ge x$ intersect at $(\frac{n}{2},\frac{n}{2})$, but that value is not an integer. By symmetry, for each of the four line segments from the diagonal, there are $\frac{n+1}{2}$ lattice points. Since there are a total of $(n+1)^2$ lattice points within $0 \le x,y \le n$, by symmetry, each section formed from the diagonals has $\frac{(n+1)^2 - 2n - 2}{4} = \frac{n^2 - 1}{4}$ lattice points. We want the points on lines $y = n$, $y = x$ and not $x+y=n$, so there are $\frac{n^2 + 2n + 1}{4}$ points that satisfy the conditions if $n$ is odd.

In summary, the number of triangles that satisfy the conditions are $\boxed{\frac{n^2 + 2n}{4} (n \text{ is even)}}$ and $\boxed{\frac{n^2 + 2n + 1}{4} (n \text{ is odd)}}$, or $\boxed{\lceil \frac{n^2 + 2n}{4} \rceil}$

See Also

2005 Indonesia MO (Problems)
Preceded by
First Problem
1 2 3 4 5 6 7 8 Followed by
Problem 2
All Indonesia MO Problems and Solutions