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 "2009 AIME I Problems/Problem 11"

(→‎Solution)
(→‎Solution)
Line 3: Line 3:
 
Consider the set of all triangles <math>OPQ</math> where <math>O</math> is the origin and <math>P</math> and <math>Q</math> are distinct points in the plane with nonnegative integer coordinates <math>(x,y)</math> such that <math>41x + y = 2009</math>. Find the number of such distinct triangles whose area is a positive integer.
 
Consider the set of all triangles <math>OPQ</math> where <math>O</math> is the origin and <math>P</math> and <math>Q</math> are distinct points in the plane with nonnegative integer coordinates <math>(x,y)</math> such that <math>41x + y = 2009</math>. Find the number of such distinct triangles whose area is a positive integer.
  
−
== Solution ==
+
== Solution 1 ==
 
Let the two points <math>P</math> and <math>Q</math> be defined with coordinates; <math>P=(x_1,y_1)</math> and <math>Q=(x_2,y_2)</math>
 
Let the two points <math>P</math> and <math>Q</math> be defined with coordinates; <math>P=(x_1,y_1)</math> and <math>Q=(x_2,y_2)</math>
  
Line 17: Line 17:
  
 
Since <math>2009</math> is not even, <math>((x_1)-(x_2))</math> must be even, thus the two <math>x</math>'s must be of the same parity. Also note that the maximum value for <math>x</math> is <math>49</math> and the minimum is <math>0</math>. There are <math>25</math> even and <math>25</math> odd numbers available for use as coordinates and thus there are <math>(_{25}C_2)+(_{25}C_2)=\boxed{600}</math> such triangles.
 
Since <math>2009</math> is not even, <math>((x_1)-(x_2))</math> must be even, thus the two <math>x</math>'s must be of the same parity. Also note that the maximum value for <math>x</math> is <math>49</math> and the minimum is <math>0</math>. There are <math>25</math> even and <math>25</math> odd numbers available for use as coordinates and thus there are <math>(_{25}C_2)+(_{25}C_2)=\boxed{600}</math> such triangles.
 +
 +
== Solution 2 ==
 +
As in the solution above, let the two points <math>P</math> and <math>Q</math> be defined with coordinates; <math>P=(x_1,y_1)</math> and <math>Q=(x_2,y_2)</math>.
 +
 +
 +
If the coordinates of <math>P</math> and <math>Q</math> have nonnegative integer coordinates, <math>P</math> and <math>Q</math> must be lattice points either
 +
 +
*on the nonnegative x-axis
 +
 +
*on the nonnegative y-axis
 +
 +
*in the first quadrant
 +
 +
We can calculate the y-intercept of the line <math>41x+y=2009</math> to be <math>(0,2009)</math> and the x-intercept to be <math>(49,0)</math>.
 +
 +
Using the point-to-line distance formula, we can calculate the height of <math>\triangle OPQ</math> from vertex <math>O</math> (the origin) to be:
 +
 +
<math>\dfrac{|41(0) + 1(0) - 2009|}{\sqrt{41^2 + 1^2}} = \dfrac{2009}{\sqrt{1682}} = \dfrac{2009}{29\sqrt2}</math>
 +
 +
Let <math>b</math> be the base of the triangle that is part of the line <math>41x+y=2009</math>.
 +
 +
The area is calculated as:
 +
<math>\dfrac{1}{2}\times b \times \dfrac{2009}{29\sqrt2} = \dfrac{2009}{58\sqrt2}\times b</math>
 +
 +
Let the numerical area of the triangle be <math>k</math>.
 +
 +
So, <math>k = \dfrac{2009}{58\sqrt2}\times b</math>
 +
 +
We know that <math>k</math> is an integer. So, <math>b = 58\sqrt2 \times z</math>, where <math>z</math> is also an integer.
 +
 +
We defined the points <math>P</math> and <math>Q</math> as <math>P=(x_1,y_1)</math> and <math>Q=(x_2,y_2)</math>.
 +
 +
Changing the y-coordinates to be in terms of x, we get:
 +
 +
<math>P=(x_1,2009-41x_1)</math> and <math>Q=(x_2,2009-41x_2)</math>.
 +
 +
The distance between them equals <math>b</math>.
 +
 +
Using the distance formula, we get
 +
 +
<math>PQ = b = \sqrt{(-41x_2+ 41x_1)^2 + (x_2 - x_1)^2} = 29\sqrt2 \times |x_2 - x_1| = 58\sqrt2\times z</math> (*)
 +
 +
WLOG, we can assume that <math>x_2 > x_1</math>.
 +
 +
Taking the last two equalities from the <math>(*)</math> string of equalities and putting in our assumption that <math>x_2>x_1</math>, we get
 +
 +
<math>29\sqrt2\times (x_2-x_1) = 58\sqrt2\times z</math>.
 +
 +
Dividing both sides by <math>29\sqrt2</math>, we get
 +
 +
<math>x_2-x_1 = 2z</math>
 +
 +
As we mentioned, <math>z</math> is an integer, so <math>x_2-x_1</math> is an even integer. Also, <math>x_2</math> and <math>x_1</math> are both positive integers. So, <math>x_2</math> and <math>x_1</math> are between 0 and 49, inclusive. Also, <math>x_2>x_1</math>.
 +
 +
*There are 48 ordered pairs <math>(x_2,x_1)</math> such that their positive difference is 2.
 +
 +
*There are 46 ordered pairs <math>(x_2,x_1)</math> such that their positive difference is 4.
 +
 +
...
 +
 +
*Finally, there are 2 ordered pairs <math>(x_2,x_1)</math> such that their positive difference is 48.
 +
 +
Summing them up, we get that there are <math>2+4+\dots + 48 = \boxed{600}</math> triangles.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=10|num-a=12}}
 
{{AIME box|year=2009|n=I|num-b=10|num-a=12}}

Revision as of 15:07, 25 March 2012

Problem

Consider the set of all triangles $OPQ$ where $O$ is the origin and $P$ and $Q$ are distinct points in the plane with nonnegative integer coordinates $(x,y)$ such that $41x + y = 2009$. Find the number of such distinct triangles whose area is a positive integer.

Solution 1

Let the two points $P$ and $Q$ be defined with coordinates; $P=(x_1,y_1)$ and $Q=(x_2,y_2)$

We can calculate the area of the parallelogram with the determinant of the matrix of the coordinates of the two points(shoelace theorem).

$\det \left({\matrix {P \above Q}}\right)=\det \left({\matrix {x_1 \above x_2}\matrix {y_1 \above y_2}\right).$ (Error compiling LaTeX. Unknown error_msg)

Since the triangle has half the area of the parallelogram, we just need the determinant to be even.

The determinant is

\[(x_1)(y_2)-(x_2)(y_1)=(x_1)(2009-41(x_2))-(x_2)(2009-41(x_1))=2009(x_1)-41(x_1)(x_2)-2009(x_2)+41(x_1)(x_2)=2009((x_1)-(x_2))\]

Since $2009$ is not even, $((x_1)-(x_2))$ must be even, thus the two $x$'s must be of the same parity. Also note that the maximum value for $x$ is $49$ and the minimum is $0$. There are $25$ even and $25$ odd numbers available for use as coordinates and thus there are $(_{25}C_2)+(_{25}C_2)=\boxed{600}$ such triangles.

Solution 2

As in the solution above, let the two points $P$ and $Q$ be defined with coordinates; $P=(x_1,y_1)$ and $Q=(x_2,y_2)$.


If the coordinates of $P$ and $Q$ have nonnegative integer coordinates, $P$ and $Q$ must be lattice points either

  • on the nonnegative x-axis
  • on the nonnegative y-axis
  • in the first quadrant

We can calculate the y-intercept of the line $41x+y=2009$ to be $(0,2009)$ and the x-intercept to be $(49,0)$.

Using the point-to-line distance formula, we can calculate the height of $\triangle OPQ$ from vertex $O$ (the origin) to be:

$\dfrac{|41(0) + 1(0) - 2009|}{\sqrt{41^2 + 1^2}} = \dfrac{2009}{\sqrt{1682}} = \dfrac{2009}{29\sqrt2}$

Let $b$ be the base of the triangle that is part of the line $41x+y=2009$.

The area is calculated as: $\dfrac{1}{2}\times b \times \dfrac{2009}{29\sqrt2} = \dfrac{2009}{58\sqrt2}\times b$

Let the numerical area of the triangle be $k$.

So, $k = \dfrac{2009}{58\sqrt2}\times b$

We know that $k$ is an integer. So, $b = 58\sqrt2 \times z$, where $z$ is also an integer.

We defined the points $P$ and $Q$ as $P=(x_1,y_1)$ and $Q=(x_2,y_2)$.

Changing the y-coordinates to be in terms of x, we get:

$P=(x_1,2009-41x_1)$ and $Q=(x_2,2009-41x_2)$.

The distance between them equals $b$.

Using the distance formula, we get

$PQ = b = \sqrt{(-41x_2+ 41x_1)^2 + (x_2 - x_1)^2} = 29\sqrt2 \times |x_2 - x_1| = 58\sqrt2\times z$ (*)

WLOG, we can assume that $x_2 > x_1$.

Taking the last two equalities from the $(*)$ string of equalities and putting in our assumption that $x_2>x_1$, we get

$29\sqrt2\times (x_2-x_1) = 58\sqrt2\times z$.

Dividing both sides by $29\sqrt2$, we get

$x_2-x_1 = 2z$

As we mentioned, $z$ is an integer, so $x_2-x_1$ is an even integer. Also, $x_2$ and $x_1$ are both positive integers. So, $x_2$ and $x_1$ are between 0 and 49, inclusive. Also, $x_2>x_1$.

  • There are 48 ordered pairs $(x_2,x_1)$ such that their positive difference is 2.
  • There are 46 ordered pairs $(x_2,x_1)$ such that their positive difference is 4.

...

  • Finally, there are 2 ordered pairs $(x_2,x_1)$ such that their positive difference is 48.

Summing them up, we get that there are $2+4+\dots + 48 = \boxed{600}$ triangles.

See also

2009 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_11&oldid=45749"