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 AIME II Problems/Problem 7"

(→‎Solution 1)
m (→‎Solution 2)
Line 43: Line 43:
  
 
==Solution 2==
 
==Solution 2==
−
Using the steps of the previous solution we get <math>c = \sum_{i=1}^{2009} {2i\choose i} \cdot 2^{2\cdot 2009 - 2i}</math> and if you do the small cases(like <math>1, 2, 3, 4, 5, 6</math>) you realize that youu can "thin-slice" the problem and simply look at the cases where <math>i=2009, 2008</math>(they're nearly identical in nature but one has <math>4</math> with it) since <math>\dbinom{2i}{I}</math> hardly contains any powers of <math>2</math> or in other words it's very inefficient and the inefficient cases hold all the power so you can just look at the highest powers of <math>2</math> in <math>\dbinom{4018}{2009}</math> and <math>\dbinom{4016}{2008}</math> and you get the minimum power of <math>2</math> in either expression is <math>8</math> so the answer is <math>\frac{4010}{10} \implies \boxed{401}</math> since it would violate the rules of the AIME and the small cases if <math>b>1</math>.
+
Using the steps of the previous solution we get <math>c = \sum_{i=1}^{2009} {2i\choose i} \cdot 2^{2\cdot 2009 - 2i}</math> and if you do the small cases(like <math>1, 2, 3, 4, 5, 6</math>) you realize that you can "thin-slice" the problem and simply look at the cases where <math>i=2009, 2008</math>(they're nearly identical in nature but one has <math>4</math> with it) since <math>\dbinom{2i}{I}</math> hardly contains any powers of <math>2</math> or in other words it's very inefficient and the inefficient cases hold all the power so you can just look at the highest powers of <math>2</math> in <math>\dbinom{4018}{2009}</math> and <math>\dbinom{4016}{2008}</math> and you get the minimum power of <math>2</math> in either expression is <math>8</math> so the answer is <math>\frac{4010}{10} \implies \boxed{401}</math> since it would violate the rules of the AIME and the small cases if <math>b>1</math>.
  
 
== See Also ==
 
== See Also ==

Revision as of 17:47, 16 December 2018

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 1

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 denominator 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}$.

Additionally, once you count the number of factors of $2$ in the summation, one can consider the fact that, since $b$ must be odd, it has to take on a value of $1,3,5,7,$ or $9$ (Because the number of $2$s in the summation is clearly greater than $1000$, dividing by $10$ will yield a number greater than $100$, and multiplying this number by any odd number greater than $9$ will yield an answer $>999$, which cannot happen on the AIME.) Once you calculate the value of $4010$, and divide by $10$, $b$ must be equal to $1$, as any other value of $b$ will result in an answer $>999$. This gives $\boxed{401}$ as the answer.

Just a small note. It's important to note the properties of the $v_p$ function, which is what Solution 1 is using but denoting it as $p (...)$. We want to calculate $v_2 \left( \sum ^{2009} _{i=1} \dbinom{2i}{i} \cdot 2^{2 \cdot 2009 - 2i} \right)$ as the final step. We know that one property of $v_p$ is that $v_p (a + b) \geq \min \left( v_p(a), v_p (b) \right)$. Therefore, we have that $v_2 \left( \sum ^{2009} _{i=1} \dbinom{2i}{i} \cdot 2^{2 \cdot 2009 - 2i} \right) \geq \min \left( 2 \cdot 2009 -1, 2 \cdot 2009 -2 - 1, ... , 2 \cdot 2009 - 2008 - v_2 (2008!), 2 \cdot 2009 - 2009 - v_2 (2009!) \right)$. Thus, we see by similar calculations as in Solution 1, that $v_2 (c) \geq 8$. From which the conclusion follows.

- (OmicronGamma)

Solution 2

Using the steps of the previous solution we get $c = \sum_{i=1}^{2009} {2i\choose i} \cdot 2^{2\cdot 2009 - 2i}$ and if you do the small cases(like $1, 2, 3, 4, 5, 6$) you realize that you can "thin-slice" the problem and simply look at the cases where $i=2009, 2008$(they're nearly identical in nature but one has $4$ with it) since $\dbinom{2i}{I}$ hardly contains any powers of $2$ or in other words it's very inefficient and the inefficient cases hold all the power so you can just look at the highest powers of $2$ in $\dbinom{4018}{2009}$ and $\dbinom{4016}{2008}$ and you get the minimum power of $2$ in either expression is $8$ so the answer is $\frac{4010}{10} \implies \boxed{401}$ since it would violate the rules of the AIME and the small cases if $b>1$.

See Also

2009 AIME II (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_7&oldid=99494"