Art of Problem Solving
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

Mock AIME 1 2007-2008 Problems/Problem 6: Difference between revisions

← Older edit
Zzyzx (talk | contribs)
10 edits
Egong2012 (talk | contribs)
editor
3 edits
 
(4 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}{\cdot 2008^2} \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://wiki.aopstest.com/wiki/index.php?title=Mock_AIME_1_2007-2008_Problems/Problem_6&oldid=219066"