Difference between revisions of "2009 AIME II Problems/Problem 7"

m (Solution)
Line 22: Line 22:
  
 
It immediately follows that <math>p\left( {2i\choose i} \right) = p((2i)!) - 2p(i!) = i - p(i!)</math>,
 
It immediately follows that <math>p\left( {2i\choose i} \right) = p((2i)!) - 2p(i!) = i - p(i!)</math>,
and hence <math>p\left( {2i\choose i} \cdot 2^{2\cdot 2009 - 2i} \right) = 2\cdot 2009 - i - p(i!)}</math>.  
+
and hence <math>p\left( {2i\choose i} \cdot 2^{2\cdot 2009 - 2i} \right) = 2\cdot 2009 - i - p(i!)</math>.  
  
 
Obviously, for <math>i\in\{1,2,\dots,2009\}</math> the function <math>f(i)=2\cdot 2009 - i - p(i!)</math> is is a strictly decreasing function.  
 
Obviously, for <math>i\in\{1,2,\dots,2009\}</math> the function <math>f(i)=2\cdot 2009 - i - p(i!)</math> is is a strictly decreasing function.  

Revision as of 22:47, 10 March 2015

Problem

Define $n!!$ to be $n(n-2)(n-4)\cdots 3\cdot 1$ for $n$ odd and $n(n-2)(n-4)\cdots 4\cdot 2$ for $n$ even. When $\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}$ is expressed as a fraction in lowest terms, its denominator is $2^ab$ with $b$ odd. Find $\dfrac{ab}{10}$.

Solution

First, note that $(2n)!! = 2^n \cdot n!$, and that $(2n)!! \cdot (2n-1)!! = (2n)!$.

We can now take the fraction $\dfrac{(2i-1)!!}{(2i)!!}$ and multiply both the numerator and the denumerator by $(2i)!!$. We get that this fraction is equal to $\dfrac{(2i)!}{(2i)!!^2} = \dfrac{(2i)!}{2^{2i}(i!)^2}$.

Now we can recognize that $\dfrac{(2i)!}{(i!)^2}$ is simply ${2i \choose i}$, hence this fraction is $\dfrac{{2i\choose i}}{2^{2i}}$, and our sum turns into $S=\sum_{i=1}^{2009} \dfrac{{2i\choose i}}{2^{2i}}$.

Let $c = \sum_{i=1}^{2009} {2i\choose i} \cdot 2^{2\cdot 2009 - 2i}$. Obviously $c$ is an integer, and $S$ can be written as $\dfrac{c}{2^{2\cdot 2009}}$. Hence if $S$ is expressed as a fraction in lowest terms, its denominator will be of the form $2^a$ for some $a\leq 2\cdot 2009$.

In other words, we just showed that $b=1$. To determine $a$, we need to determine the largest power of $2$ that divides $c$.

Let $p(i)$ be the largest $x$ such that $2^x$ that divides $i$.

We can now return to the observation that $(2i)! = (2i)!! \cdot (2i-1)!! = 2^i \cdot i! \cdot (2i-1)!!$. Together with the obvious fact that $(2i-1)!!$ is odd, we get that $p((2i)!)=p(i!)+i$.

It immediately follows that $p\left( {2i\choose i} \right) = p((2i)!) - 2p(i!) = i - p(i!)$, and hence $p\left( {2i\choose i} \cdot 2^{2\cdot 2009 - 2i} \right) = 2\cdot 2009 - i - p(i!)$.

Obviously, for $i\in\{1,2,\dots,2009\}$ the function $f(i)=2\cdot 2009 - i - p(i!)$ is is a strictly decreasing function. Therefore $p(c) = p\left( {2\cdot 2009\choose 2009} \right) = 2009 - p(2009!)$.

We can now compute $p(2009!) = \sum_{k=1}^{\infty} \left\lfloor \dfrac{2009}{2^k} \right\rfloor = 1004 + 502 + \cdots + 3 + 1 = 2001$. Hence $p(c)=2009-2001=8$.

And thus we have $a=2\cdot 2009 - p(c) = 4010$, and the answer is $\dfrac{ab}{10} = \dfrac{4010\cdot 1}{10} = \boxed{401}$.

See Also

2009 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 6
Followed by
Problem 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png