Difference between revisions of "2009 AMC 12B Problems/Problem 22"

Revision as of 18:14, 11 November 2015

Problem

Parallelogram $ABCD$ has area $1,\!000,\!000$ . Vertex $A$ is at $(0,0)$ and all other vertices are in the first quadrant. Vertices $B$ and $D$ are lattice points on the lines $y = x$ and $y = kx$ for some integer $k > 1$ , respectively. How many such parallelograms are there?

$\textbf{(A)}\ 49\qquad \textbf{(B)}\ 720\qquad \textbf{(C)}\ 784\qquad \textbf{(D)}\ 2009\qquad \textbf{(E)}\ 2048$

Solution

Solution 1

The area of any parallelogram $ABCD$ can be computed as the size of the vector product of $\overrightarrow{AB}$ and $\overrightarrow{AD}$ .

In our setting where $A=(0,0)$ , $B=(s,s)$ , and $D=(t,kt)$ this is simply $s\cdot kt - s\cdot t = (k-1)st$ .

In other words, we need to count the triples of integers $(k,s,t)$ where $k>1$ , $s,t>0$ and $(k-1)st = 1,\!000,\!000 = 2^6 5^6$ .

These can be counted as follows: We have $6$ identical red balls (representing powers of $2$ ), $6$ blue balls (representing powers of $5$ ), and three labeled urns (representing the factors $k-1$ , $s$ , and $t$ ). The red balls can be distributed in ${8\choose 2} = 28$ ways, and for each of these ways, the blue balls can then also be distributed in $28$ ways. (See Distinguishability for a more detailed explanation.)

Thus there are exactly $28^2 = 784$ ways how to break $1,\!000,\!000$ into three positive integer factors, and for each of them we get a single parallelogram. Hence the number of valid parallelograms is $\boxed{784}$ .

Solution 2

Without the vector product the area of $ABCD$ can be computed for example as follows: If $B=(s,s)$ and $D=(t,kt)$ , then clearly $C=(s+t,s+kt)$ . Let $B'=(s,0)$ , $C'=(s+t,0)$ and $D'=(t,0)$ be the orthogonal projections of $B$ , $C$ , and $D$ onto the $x$ axis. Let $[P]$ denote the area of the polygon $P$ . We can then compute:

$\begin{align*} [ABCD] & = [ADD'] + [DD'C'C] - [BB'C'C] - [ABB'] \\ & = \frac{kt^2}2 + \frac{s(s+2kt)}2 - \frac{t(2s+kt)}2 - \frac{s^2}2 \\ & = kst - st \\ & = (k-1)st. \end{align*}$ The remainder of the solution is the same as the above.

@@ Line 1: / Line 1: @@
 == Problem ==
-Parallelogram <math>ABCD</math> has area <math>1,\!000,\!000</math>. Vertex <math>A</math> is at <math>(0,0)</math> and all other vertices are in the first quadrant. Vertices <math>B</math> and <math>D</math> are lattice points on the lines <math>y = x</math> and <math>y = kx</math> for some integer <math>k > 1</math>, respectively. How many such parallelograms are there?
+<!-- don't remove the following tag, for PoTW on the Wiki front page--><onlyinclude>Parallelogram <math>ABCD</math> has area <math>1,\!000,\!000</math>. Vertex <math>A</math> is at <math>(0,0)</math> and all other vertices are in the first quadrant. Vertices <math>B</math> and <math>D</math> are lattice points on the lines <math>y = x</math> and <math>y = kx</math> for some integer <math>k > 1</math>, respectively. How many such parallelograms are there?<!-- don't remove the following tag, for PoTW on the Wiki front page--></onlyinclude>
 <math>\textbf{(A)}\ 49\qquad \textbf{(B)}\ 720\qquad \textbf{(C)}\ 784\qquad \textbf{(D)}\ 2009\qquad \textbf{(E)}\ 2048</math>

2009 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 21	Followed by Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search