Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 Indonesia MO Problems/Problem 1"

(Solution to Problem 1 — back at it again)
 
m (→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 59: Line 59:
 
The line <math>x+y>n</math> and <math>y \ge x</math> intersect at <math>(\frac{n}{2},\frac{n}{2})</math>, but that value is not an integer.  By symmetry, for each of the four line segments from the diagonal, there are <math>\frac{n+1}{2}</math> lattice points.  Since there are a total of <math>(n+1)^2</math> lattice points within <math>0 \le x,y \le n</math>, by symmetry, each section formed from the diagonals has <math>\frac{(n+1)^2 - 2n - 2}{4} = \frac{n^2 - 1}{4}</math> lattice points.  We want the points on lines <math>y = n</math>, <math>y = x</math> and not <math>x+y=n</math>, so there are <math>\frac{n^2 + 2n + 1}{4}</math> points that satisfy the conditions if <math>n</math> is odd.
 
The line <math>x+y>n</math> and <math>y \ge x</math> intersect at <math>(\frac{n}{2},\frac{n}{2})</math>, but that value is not an integer.  By symmetry, for each of the four line segments from the diagonal, there are <math>\frac{n+1}{2}</math> lattice points.  Since there are a total of <math>(n+1)^2</math> lattice points within <math>0 \le x,y \le n</math>, by symmetry, each section formed from the diagonals has <math>\frac{(n+1)^2 - 2n - 2}{4} = \frac{n^2 - 1}{4}</math> lattice points.  We want the points on lines <math>y = n</math>, <math>y = x</math> and not <math>x+y=n</math>, so there are <math>\frac{n^2 + 2n + 1}{4}</math> points that satisfy the conditions if <math>n</math> is odd.
  
−
In summary, the number of triangles that satisfy the conditions are <math>\boxed{\frac{n^2 + 2n}{4} (n \text{ is even)}}</math> and <math>\boxed{\frac{n^2 + 2n + 1}{4} (n \text{ is odd)}}</math>.
+
In summary, the number of triangles that satisfy the conditions are <math>\boxed{\frac{n^2 + 2n}{4} (n \text{ is even)}}</math> and <math>\boxed{\frac{n^2 + 2n + 1}{4} (n \text{ is odd)}}</math>, or <math>\boxed{\lceil \frac{n^2 + 2n}{4} \rceil}</math>
  
 
==See Also==
 
==See Also==

Latest revision as of 00:17, 3 February 2023

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_1&oldid=188542"