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)
 
(23 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
 
 
== Problem ==
 
== Problem ==
 
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 (Matrix's, Determinants) ==
−
Solution 1 (This solution requires linear algeber knowledgw)
+
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>
 +
 
 +
We can calculate the area of the parallelogram with the determinant of the matrix of the coordinates of the two points(shoelace theorem).
 +
 
 +
<math>\det \left(\begin{array}{c} P \\ Q\end{array}\right)=\det \left(\begin{array}{cc}x_1 &y_1\\x_2&y_2\end{array}\right).</math>
 +
 
 +
Since the triangle has half the area of the parallelogram, we just need the determinant to be even.
 +
 
 +
The determinant is
 +
 
 +
<cmath>(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))</cmath>
 +
 
 +
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 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 line <math>41x+y=2009</math> intersect the x-axis at <math>X</math> and the y-axis at <math>Y</math>. <math>X</math> has coordinates <math>(49,0)</math>, and <math>Y</math> has coordinates <math>(0,2009)</math>. As such, there are exactly <math>50</math> lattice points on this line that can be used for <math>P</math> and <math>Q</math>.
 +
 
 +
 
 +
 
 +
WLOG, let the x-coordinate of <math>P</math> be less than the x-coordinate of <math>Q</math>. Note that <math>[OPQ]=[OYX]-[OYP]-[OXQ]</math>. We know that <math>OY=2009</math> and <math>OX= 49</math>; as such, <math>[OYX]=\frac{1}{2} \cdot OY \cdot OX = \frac{1}{2} \cdot 2009 \cdot 49</math>. In addition, <math>[OYP]=\frac{1}{2} \cdot 2009 \cdot x_1</math> and <math>[OXQ]=\frac{1}{2} \cdot 49 \cdot y_2</math>.
 +
 
 +
 
 +
Since <math>2009 \cdot 49</math> is odd, the total area of <math>OYX</math> is not an integer; rather, it is of the form <math>k + \frac{1}{2}</math> where <math>k</math> is an integer. To ensure <math>[OPQ]</math> has an integral value, exactly one of <math>[OPY]</math> and <math>[OQX]</math> must have an integral value as well (the other must be of the form <math>k + \frac{1}{2}</math> where <math>k</math> is an integer).
 +
 
 +
 
 +
Returning to <math>41x+y=2009</math>, we notice that integer pairs of <math>x</math> and <math>y</math> that satisfy the equation always have different parities. To satisfy exactly one of <math>[OPY]</math> and <math>[OQX]</math> having an integral area, we must have <math>x_1</math> and <math>y_2</math> having different parities. This is because having an even number for <math>x_1</math> or <math>y_2</math> makes the area of the triangle an integer. We can therefore deduce that <math>x_1</math> and <math>x_2</math> have the same parity.
 +
 
 +
Out of the <math>50</math> usable lattice points for <math>P</math> and <math>Q</math>, <math>25</math> have even x-coordinates and <math>25</math> have odd x-coordinates. Since we must pick two points with even x-coordinates or two points with odd x-coordinates, our desired answer is <math>\binom{25}{2}+\binom{25}{2}=300+300=\fbox{600}</math>.
 +
 
 +
== Solution 3 (Analytic geometry) ==
 +
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>.
  
−
Let the two points be point P and Q
+
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:
  
−
and <math>P=(x_1,y_1),Q=(x_2,y_2)</math>
+
<math>\dfrac{|41(0) + 1(0) - 2009|}{\sqrt{41^2 + 1^2}} = \dfrac{2009}{\sqrt{1682}} = \dfrac{2009}{29\sqrt2}</math>
  
−
We can calculate the area of the parallelogram span with the determinant of matrix
+
Let <math>b</math> be the base of the triangle that is part of the line <math>41x+y=2009</math>.
  
−
<math>\det ({\matrix {P \above Q}})=\det </math><math>({\matrix {x_1 \above x_2} \right \matrix {y_1  \above y_2})</math>
+
The area is calculated as:
 +
<math>\dfrac{1}{2}\times b \times \dfrac{2009}{29\sqrt2} = \dfrac{2009}{58\sqrt2}\times b</math>
  
−
since triangle is half of the area of the parallelogram. We just need the determinant to be even
+
Let the numerical area of the triangle be <math>k</math>.  
  
−
The deteminant is
+
So, <math>k = \dfrac{2009}{58\sqrt2}\times b</math>
  
−
<cmath>(x_1)(y_2)-(x_2)(y_1)=(x_1)(2009-41(x_2))-(x_2)(2009-41(x_1))</cmath>
+
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.
  
−
<cmath>=2009(x_1)-41(x_1)(x_2)-2009(x_2)+41(x_1)(x_2)=2009((x_1)-(x_2))</cmath>
+
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>.
  
−
since 2009 is not even, <math>((x_1)-(x_2))</math> must be even
+
Changing the y-coordinates to be in terms of x, we get:
  
−
Thus the two x's have to be both odd or even.
+
<math>P=(x_1,2009-41x_1)</math> and <math>Q=(x_2,2009-41x_2)</math>.
  
−
Also note that the maximum value for x is <math>49</math> and minimum is <math>0</math>.
+
The distance between them equals <math>b</math>.  
  
−
There are <math>25</math> even and <math>25</math> odd number
+
Using the distance formula, we get
  
−
Thus, there are
+
<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> <math>(*)</math>
  
−
<math>(_{25}C_2)+(_{25}C_2)=\boxed{600}</math>of such triangle
+
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. Remember, <math>x_2>x_1</math> as well.
 +
 
 +
*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.
 +
 
 +
== Solution 4 ==
 +
 
 +
We present a non-analytic solution; consider the lattice points on the line <math>41x+y=2009</math>. The line has intercepts <math>(0, 2009)</math> and <math>(49, 0)</math>, so the lattice points for <math>x=0, 1, \ldots, 49</math> divide the line into <math>49</math> equal segments. Call the area of the large triangle <math>A</math>. Any triangle formed with the origin having a base of one of these segments has area <math>A/49</math> (call this value <math>B</math>) because the height is the same as that of large triangle, and the bases are in the ratio <math>1:49</math>. A segment comprised of <math>n</math> small segments (all adjacent to each other) will have area <math>nB</math>. Rewriting in terms of the original area, <math>A=(\frac{1}{2})(49)(2009)</math>, <math>B=\frac{2009}{2}</math>, and <math>nB=n(\frac{2009}{2})</math>. It is clear that in order to have a nonnegative integer for <math>nB</math> as desired, <math>n</math> must be even. This is equivalent to finding the number of ways to choose two distinct <math>x</math>-values <math>x_1</math> and <math>x_2</math> (<math>0 \leq x_1, x_2 \leq 49</math>) such that their positive difference (<math>n</math>) is even. Follow one of the previous methods above to choose these pairs and arrive at the answer of 600.
  
 
== 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}}
 +
 +
[[Category:Intermediate Geometry Problems]]
 +
{{MAA Notice}}

Latest revision as of 14:01, 16 August 2020

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 (Matrix's, Determinants)

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(\begin{array}{c} P \\ Q\end{array}\right)=\det \left(\begin{array}{cc}x_1 &y_1\\x_2&y_2\end{array}\right).$

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 Solution 1, let the two points $P$ and $Q$ be defined with coordinates; $P=(x_1,y_1)$ and $Q=(x_2,y_2)$. Let the line $41x+y=2009$ intersect the x-axis at $X$ and the y-axis at $Y$. $X$ has coordinates $(49,0)$, and $Y$ has coordinates $(0,2009)$. As such, there are exactly $50$ lattice points on this line that can be used for $P$ and $Q$.


WLOG, let the x-coordinate of $P$ be less than the x-coordinate of $Q$. Note that $[OPQ]=[OYX]-[OYP]-[OXQ]$. We know that $OY=2009$ and $OX= 49$; as such, $[OYX]=\frac{1}{2} \cdot OY \cdot OX = \frac{1}{2} \cdot 2009 \cdot 49$. In addition, $[OYP]=\frac{1}{2} \cdot 2009 \cdot x_1$ and $[OXQ]=\frac{1}{2} \cdot 49 \cdot y_2$.


Since $2009 \cdot 49$ is odd, the total area of $OYX$ is not an integer; rather, it is of the form $k + \frac{1}{2}$ where $k$ is an integer. To ensure $[OPQ]$ has an integral value, exactly one of $[OPY]$ and $[OQX]$ must have an integral value as well (the other must be of the form $k + \frac{1}{2}$ where $k$ is an integer).


Returning to $41x+y=2009$, we notice that integer pairs of $x$ and $y$ that satisfy the equation always have different parities. To satisfy exactly one of $[OPY]$ and $[OQX]$ having an integral area, we must have $x_1$ and $y_2$ having different parities. This is because having an even number for $x_1$ or $y_2$ makes the area of the triangle an integer. We can therefore deduce that $x_1$ and $x_2$ have the same parity.

Out of the $50$ usable lattice points for $P$ and $Q$, $25$ have even x-coordinates and $25$ have odd x-coordinates. Since we must pick two points with even x-coordinates or two points with odd x-coordinates, our desired answer is $\binom{25}{2}+\binom{25}{2}=300+300=\fbox{600}$.

Solution 3 (Analytic geometry)

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. Remember, $x_2>x_1$ as well.

  • 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.

Solution 4

We present a non-analytic solution; consider the lattice points on the line $41x+y=2009$. The line has intercepts $(0, 2009)$ and $(49, 0)$, so the lattice points for $x=0, 1, \ldots, 49$ divide the line into $49$ equal segments. Call the area of the large triangle $A$. Any triangle formed with the origin having a base of one of these segments has area $A/49$ (call this value $B$) because the height is the same as that of large triangle, and the bases are in the ratio $1:49$. A segment comprised of $n$ small segments (all adjacent to each other) will have area $nB$. Rewriting in terms of the original area, $A=(\frac{1}{2})(49)(2009)$, $B=\frac{2009}{2}$, and $nB=n(\frac{2009}{2})$. It is clear that in order to have a nonnegative integer for $nB$ as desired, $n$ must be even. This is equivalent to finding the number of ways to choose two distinct $x$-values $x_1$ and $x_2$ ($0 \leq x_1, x_2 \leq 49$) such that their positive difference ($n$) is even. Follow one of the previous methods above to choose these pairs and arrive at the answer of 600.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_11&oldid=131935"