AMC12 2009 12B, Problem 22

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

Solution: 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 \fbox{784}$.

Answer: 784