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 "Mock AIME 1 2007-2008 Problems/Problem 6"

(→‎Solution)
(→‎Problem 6)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
== Problem 6 ==
+
what the sigma
−
A <math>\frac 1p</math> -array is a structured, infinite, collection of numbers. For example, a <math>\frac 13</math> -array is constructed as follows:
 
−
 
−
<center><math>\begin{align*}
 
−
1 \qquad \frac 13\,\ \qquad \frac 19\,\ \qquad \frac 1{27} \qquad &\cdots\\
 
−
\frac 16 \qquad \frac 1{18}\,\ \qquad \frac{1}{54} \qquad &\cdots\\
 
−
\frac 1{36} \qquad \frac 1{108} \qquad &\cdots\\
 
−
\frac 1{216} \qquad &\cdots\\
 
−
&\ddots
 
−
\end{align*}</math></center>
 
−
 
−
In general, the first entry of each row is <math>\frac{1}{2p}</math> times the first entry of the previous row. Then, each succeeding term in a row is <math>\frac 1p</math> times the previous term in the same row. If the sum of all the terms in a <math>\frac{1}{2008}</math> -array can be written in the form <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers, find the remainder when <math>m+n</math> is divided by <math>2008</math>.
 
  
 
== Solution ==
 
== Solution ==
 
Note that the value in the <math>r</math>th row and the <math>c</math>th column is given by <math>\left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right)</math>. We wish to evaluate the summation over all <math>r,c</math>, and so the summation will be, using the formula for an infinite [[geometric series]]:
 
Note that the value in the <math>r</math>th row and the <math>c</math>th column is given by <math>\left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right)</math>. We wish to evaluate the summation over all <math>r,c</math>, and so the summation will be, using the formula for an infinite [[geometric series]]:
−
<center><math>\begin{align*}\sum_{r=1}^{\infty}\sum_{c=1}^{\infty} \left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right) &= \left(\sum_{r=1}^{\infty} \frac{1}{(2p)^r}\right)\left(\sum_{c=1}^{\infty} \frac{1}{p^c}\right)\\
+
<cmath>\begin{align*}\sum_{r=1}^{\infty}\sum_{c=1}^{\infty} \left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right) &= \left(\sum_{r=1}^{\infty} \frac{1}{(2p)^r}\right)\left(\sum_{c=1}^{\infty} \frac{1}{p^c}\right)\\
 
&= \left(\frac{1}{1-\frac{1}{2p}}\right)\left(\frac{1}{1-\frac{1}{p}}\right)\\
 
&= \left(\frac{1}{1-\frac{1}{2p}}\right)\left(\frac{1}{1-\frac{1}{p}}\right)\\
−
&= \frac{2p^2}{(2p-1)(p-1)}\end{align*}</math></center>
+
&= \frac{2p^2}{(2p-1)(p-1)}\end{align*}</cmath>
 
Taking the denominator with <math>p=2008</math> (indeed, the answer is independent of the value of <math>p</math>), we have <math>m+n \equiv 2008^2 + (2008-1)(2\cdot 2008 - 1) \equiv (-1)(-1) \equiv 1 \pmod{2008}</math> (or consider [[FOIL]]ing). The answer is <math>\boxed{001}</math>.
 
Taking the denominator with <math>p=2008</math> (indeed, the answer is independent of the value of <math>p</math>), we have <math>m+n \equiv 2008^2 + (2008-1)(2\cdot 2008 - 1) \equiv (-1)(-1) \equiv 1 \pmod{2008}</math> (or consider [[FOIL]]ing). The answer is <math>\boxed{001}</math>.
  
 
----
 
----
  
−
With less notation, the above solution is equivalent to considering the product of the geometric series <math>\left(1+\frac{1}{2 \cdot 2008} + \frac{1}{4 \cdot 2008^2} \cdots\right)\left(1 + \frac{1}{2008} + \frac{1}{2 \cdot 2008} \cdots \right)</math>. Note that when we expand this product, the terms cover all of the elements of the array.  
+
With less notation, the above solution is equivalent to considering the product of the geometric series <math>\left(1+\frac{1}{2 \cdot 2008} + \frac{1}{4 \cdot 2008^2} \cdots\right)\left(1 + \frac{1}{2008} + \frac{1}{2008^2} \cdots \right)</math>. Note that when we expand this product, the terms cover all of the elements of the array.  
  
 
By the geometric series formula, the first series evaluates to be <math>\frac{1}{1 - \frac{1}{2 \cdot 2008}} = \frac{2 \cdot 2008}{2 \cdot 2008 - 1}</math>. The second series evaluates to be <math>\frac{1}{1 - \frac{1}{2008}} = \frac{2008}{2008 - 1}</math>. Their product is <math>\frac{2008 \cdot 4016}{(2008-1)(2\cdot 2008 - 1)}</math>, from which we find that <math>m+n</math> leaves a residue of <math>1</math> upon division by <math>2008</math>.
 
By the geometric series formula, the first series evaluates to be <math>\frac{1}{1 - \frac{1}{2 \cdot 2008}} = \frac{2 \cdot 2008}{2 \cdot 2008 - 1}</math>. The second series evaluates to be <math>\frac{1}{1 - \frac{1}{2008}} = \frac{2008}{2008 - 1}</math>. Their product is <math>\frac{2008 \cdot 4016}{(2008-1)(2\cdot 2008 - 1)}</math>, from which we find that <math>m+n</math> leaves a residue of <math>1</math> upon division by <math>2008</math>.

Latest revision as of 16:35, 6 May 2024

what the sigma

Solution

Note that the value in the $r$th row and the $c$th column is given by $\left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right)$. We wish to evaluate the summation over all $r,c$, and so the summation will be, using the formula for an infinite geometric series: \begin{align*}\sum_{r=1}^{\infty}\sum_{c=1}^{\infty} \left(\frac{1}{(2p)^r}\right)\left(\frac{1}{p^c}\right) &= \left(\sum_{r=1}^{\infty} \frac{1}{(2p)^r}\right)\left(\sum_{c=1}^{\infty} \frac{1}{p^c}\right)\\ &= \left(\frac{1}{1-\frac{1}{2p}}\right)\left(\frac{1}{1-\frac{1}{p}}\right)\\ &= \frac{2p^2}{(2p-1)(p-1)}\end{align*} Taking the denominator with $p=2008$ (indeed, the answer is independent of the value of $p$), we have $m+n \equiv 2008^2 + (2008-1)(2\cdot 2008 - 1) \equiv (-1)(-1) \equiv 1 \pmod{2008}$ (or consider FOILing). The answer is $\boxed{001}$.

With less notation, the above solution is equivalent to considering the product of the geometric series $\left(1+\frac{1}{2 \cdot 2008} + \frac{1}{4 \cdot 2008^2} \cdots\right)\left(1 + \frac{1}{2008} + \frac{1}{2008^2} \cdots \right)$. Note that when we expand this product, the terms cover all of the elements of the array.

By the geometric series formula, the first series evaluates to be $\frac{1}{1 - \frac{1}{2 \cdot 2008}} = \frac{2 \cdot 2008}{2 \cdot 2008 - 1}$. The second series evaluates to be $\frac{1}{1 - \frac{1}{2008}} = \frac{2008}{2008 - 1}$. Their product is $\frac{2008 \cdot 4016}{(2008-1)(2\cdot 2008 - 1)}$, from which we find that $m+n$ leaves a residue of $1$ upon division by $2008$.

See also

Mock AIME 1 2007-2008 (Problems, Source)
Preceded by
Problem 5 		Followed by
Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2007-2008_Problems/Problem_6&oldid=219066"