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

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

Page

Toolbox

Search

2005 Indonesia MO Problems/Problem 1

Problem

Solution

See Also