Difference between revisions of "2009 AIME I Problems/Problem 11"

Revision as of 11:38, 1 April 2013

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

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.

@@ Line 82: / Line 82: @@
 == Solution 3 ==
-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 nonnegative <math>x</math>-values <math>x_1</math> and <math>x_2</math> (<math>1 \leq x_1, x_2 \leq 49</math>) such that their difference (<math>n</math>) is even. Follow one of the previous methods above to choose these pairs and arrive at the answer of 600.
+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 ==
 {{AIME box|year=2009|n=I|num-b=10|num-a=12}}

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

Page

Toolbox

Search