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 AMC 12B Problems/Problem 22"

m (→‎Solution 2)
(→‎Solution 3)
 
(11 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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? (A lattice point is any point whose coordinates are both integers.)<!-- 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>
 
<math>\textbf{(A)}\ 49\qquad \textbf{(B)}\ 720\qquad \textbf{(C)}\ 784\qquad \textbf{(D)}\ 2009\qquad \textbf{(E)}\ 2048</math>
Line 16: Line 16:
 
These can be counted as follows: We have <math>6</math> identical red balls (representing powers of <math>2</math>), <math>6</math> blue balls (representing powers of <math>5</math>), and three labeled urns (representing the factors <math>k-1</math>, <math>s</math>, and <math>t</math>). The red balls can be distributed in <math>{8\choose 2} = 28</math> ways, and for each of these ways, the blue balls can then also be distributed in <math>28</math> ways. (See [[Distinguishability]] for a more detailed explanation.)
 
These can be counted as follows: We have <math>6</math> identical red balls (representing powers of <math>2</math>), <math>6</math> blue balls (representing powers of <math>5</math>), and three labeled urns (representing the factors <math>k-1</math>, <math>s</math>, and <math>t</math>). The red balls can be distributed in <math>{8\choose 2} = 28</math> ways, and for each of these ways, the blue balls can then also be distributed in <math>28</math> ways. (See [[Distinguishability]] for a more detailed explanation.)
  
−
Thus there are exactly <math>28^2 = 784</math> ways how to break <math>1,\!000,\!000</math> into three positive integer factors, and for each of them we get a single parallelogram. Hence the number of valid parallelograms is <math>\boxed{784}</math>.
+
Thus there are exactly <math>28^2 = 784</math> ways how to break <math>1,\!000,\!000</math> into three positive integer factors, and for each of them we get a single parallelogram. Hence the number of valid parallelograms is <math>784 \longrightarrow \boxed{C}</math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
Line 34: Line 34:
 
</cmath>
 
</cmath>
 
The remainder of the solution is the same as the above.
 
The remainder of the solution is the same as the above.
 +
 +
 +
==Solution 3==
 +
We know that <math>A</math> is <math>(0, 0)</math>. Since <math>B</math> is on the line <math>y=x</math>, let it be represented by the point <math>(b, b)</math>. Similarly, let <math>D</math> be <math>(d, kd)</math>. Since this is a parallelogram, sides <math>\overline{AD}</math> and <math>\overline{BC}</math> are parallel. Therefore, the distance and relative position of <math>D</math> to <math>A</math> is equivalent to that of <math>C</math> to <math>B</math> (if we take the translation of <math>A</math> to <math>D</math> and apply it to <math>B</math>, we will get the coordinates of <math>C</math>). This yields <math>C (b+d, b+kd)</math>. Using the [[Shoelace Theorem]] we get
 +
 +
 +
<math>1,000,000 = \frac{1}{2}|\left(b(b+kd) + (b+d)(kd)\right) - \left(b(b+d) + (b+kd)d\right)|</math>
 +
 +
 +
<math>\Rightarrow 2,000,000 = |2kbd - 2bd|</math>
 +
 +
 +
<math>\Rightarrow 1,000,000 = |kbd - bd|</math>
 +
 +
 +
Since <math>k > 1, kbd > bd</math>. The equation becomes
 +
 +
 +
<math>1,000,000 = (k-1)bd</math>
 +
 +
 +
<math>\Rightarrow \frac{1,000,000}{k-1} = bd</math>
 +
 +
 +
Since <math>k</math> must be a positive integer greater than <math>1</math>, we know <math>k-1</math> will be a positive integer. We also know that <math>bd</math> is an integer, so <math>k-1</math> must be a factor of <math>1,000,000</math>. Therefore <math>bd</math> will also be a factor of <math>1,000,000</math>.
 +
 +
Notice that <math>1,000,000 = 10^6 = 2^6*5^6</math>.
 +
 +
Let <math>b</math> be <math>2^x5^y</math> such that <math>x, y</math> are integers on the interval <math>[0, 6]</math>.
 +
 +
Let <math>d</math> be <math>2^w5^z</math> such that <math>w, z</math> are integers, <math>x+w \le 6</math>, and <math>y+z \le 6</math>.
 +
 +
For a pair <math>(x, y)</math>, there are <math>7-x</math> possibilities for <math>w</math> and <math>7-y</math> possibilites for <math>z</math> (<math>d</math> doesn't have to be the co-factor of <math>1,000,000</math>, it just can't be big enough such that <math>bd > 1,000,000</math>), for a total of <math>(7-x)(7-y)</math> possibilities. So we want
 +
 +
 +
<math>\sum_{k=0, i=0}^6 (7-k)(7-i)</math>
 +
 +
 +
<math>\left(\text{the sum of the number of possible pairs}(w, z) \text{ for all pairs}(k , i)\text{ for } k[0, 6]\text{ and } i[0, 6]\right)</math>
 +
 +
 +
Notice that if we "fix" the value of <math>k</math>, at, say <math>6</math>, then run through all of the values of <math>i</math>, change the value of <math>k</math> to <math>5</math>, and run through all of the values of <math>i</math> again, and so on until we exhaust all <math>49</math> combinations of <math>(k, i)</math> we get something like this:
 +
 +
 +
<math>1*1 + 1*2 + ... + 1*6 + 1*7 + 2*1 + 2*2 + ... + 2*6 + 2*7 + ..... + 7*1 + 7*2 + ... + 7*6 + 7*7</math>
 +
 +
 +
which can be rewritten
 +
 +
 +
<math>1(1+2+...+7)+2(1+2+...+7)+.....+7(1+2+...+7)</math>
 +
 +
 +
<math>\Rightarrow (1+2+...+7)(1+2+...+7)</math>
 +
 +
 +
<math>\Rightarrow 28^2</math>
 +
 +
 +
<math>\Rightarrow 784</math>
 +
 +
 +
So there are <math>784</math> possible sets of coordinates <math>B,</math> <math>C</math>, and <math>D \Rightarrow \boxed{\text{C}}</math>.
 +
 +
Note: this solution could be greatly simplified by using the Shoelace Formula on the triangle <math>ABD</math>, which we know has half the area of the parallelogram. This eliminates the need to find the coordinates of point <math>C</math>.
 +
 +
(Notational note: I'm not sure if the notation for double index summation is correct or even applicable in the context of this problem. If someone could fix the notation so that it is correct, or replace it without changing the general content of this solution, that would be great. If the notation is correct, then just delete this footnote)
  
 
== See Also ==
 
== See Also ==

Latest revision as of 21:25, 9 October 2021

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? (A lattice point is any point whose coordinates are both integers.)

$\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 $784 \longrightarrow \boxed{C}$.

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.


Solution 3

We know that $A$ is $(0, 0)$. Since $B$ is on the line $y=x$, let it be represented by the point $(b, b)$. Similarly, let $D$ be $(d, kd)$. Since this is a parallelogram, sides $\overline{AD}$ and $\overline{BC}$ are parallel. Therefore, the distance and relative position of $D$ to $A$ is equivalent to that of $C$ to $B$ (if we take the translation of $A$ to $D$ and apply it to $B$, we will get the coordinates of $C$). This yields $C (b+d, b+kd)$. Using the Shoelace Theorem we get


$1,000,000 = \frac{1}{2}|\left(b(b+kd) + (b+d)(kd)\right) - \left(b(b+d) + (b+kd)d\right)|$


$\Rightarrow 2,000,000 = |2kbd - 2bd|$


$\Rightarrow 1,000,000 = |kbd - bd|$


Since $k > 1, kbd > bd$. The equation becomes


$1,000,000 = (k-1)bd$


$\Rightarrow \frac{1,000,000}{k-1} = bd$


Since $k$ must be a positive integer greater than $1$, we know $k-1$ will be a positive integer. We also know that $bd$ is an integer, so $k-1$ must be a factor of $1,000,000$. Therefore $bd$ will also be a factor of $1,000,000$.

Notice that $1,000,000 = 10^6 = 2^6*5^6$.

Let $b$ be $2^x5^y$ such that $x, y$ are integers on the interval $[0, 6]$.

Let $d$ be $2^w5^z$ such that $w, z$ are integers, $x+w \le 6$, and $y+z \le 6$.

For a pair $(x, y)$, there are $7-x$ possibilities for $w$ and $7-y$ possibilites for $z$ ($d$ doesn't have to be the co-factor of $1,000,000$, it just can't be big enough such that $bd > 1,000,000$), for a total of $(7-x)(7-y)$ possibilities. So we want


$\sum_{k=0, i=0}^6 (7-k)(7-i)$


$\left(\text{the sum of the number of possible pairs}(w, z) \text{ for all pairs}(k , i)\text{ for } k[0, 6]\text{ and } i[0, 6]\right)$


Notice that if we "fix" the value of $k$, at, say $6$, then run through all of the values of $i$, change the value of $k$ to $5$, and run through all of the values of $i$ again, and so on until we exhaust all $49$ combinations of $(k, i)$ we get something like this:


$1*1 + 1*2 + ... + 1*6 + 1*7 + 2*1 + 2*2 + ... + 2*6 + 2*7 + ..... + 7*1 + 7*2 + ... + 7*6 + 7*7$


which can be rewritten


$1(1+2+...+7)+2(1+2+...+7)+.....+7(1+2+...+7)$


$\Rightarrow (1+2+...+7)(1+2+...+7)$


$\Rightarrow 28^2$


$\Rightarrow 784$


So there are $784$ possible sets of coordinates $B,$ $C$, and $D \Rightarrow \boxed{\text{C}}$.

Note: this solution could be greatly simplified by using the Shoelace Formula on the triangle $ABD$, which we know has half the area of the parallelogram. This eliminates the need to find the coordinates of point $C$.

(Notational note: I'm not sure if the notation for double index summation is correct or even applicable in the context of this problem. If someone could fix the notation so that it is correct, or replace it without changing the general content of this solution, that would be great. If the notation is correct, then just delete this footnote)

See Also

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

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_AMC_12B_Problems/Problem_22&oldid=163368"