Difference between revisions of "2009 AIME II Problems/Problem 7"
(→Solution) |
|||
Line 2: | Line 2: | ||
Define <math>n!!</math> to be <math>n(n-2)(n-4)\cdots 3\cdot 1</math> for <math>n</math> odd and <math>n(n-2)(n-4)\cdots 4\cdot 2</math> for <math>n</math> even. When <math>\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}</math> is expressed as a fraction in lowest terms, its denominator is <math>2^ab</math> with <math>b</math> odd. Find <math>\dfrac{ab}{10}</math>. | Define <math>n!!</math> to be <math>n(n-2)(n-4)\cdots 3\cdot 1</math> for <math>n</math> odd and <math>n(n-2)(n-4)\cdots 4\cdot 2</math> for <math>n</math> even. When <math>\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}</math> is expressed as a fraction in lowest terms, its denominator is <math>2^ab</math> with <math>b</math> odd. Find <math>\dfrac{ab}{10}</math>. | ||
− | == Solution == | + | == Solution 1== |
First, note that <math>(2n)!! = 2^n \cdot n!</math>, and that <math>(2n)!! \cdot (2n-1)!! = (2n)!</math>. | First, note that <math>(2n)!! = 2^n \cdot n!</math>, and that <math>(2n)!! \cdot (2n-1)!! = (2n)!</math>. | ||
Line 34: | Line 34: | ||
---- | ---- | ||
Additionally, once you count the number of factors of <math>2</math> in the summation, one can consider the fact that, since <math>b</math> must be odd, it has to take on a value of <math>1,3,5,7,</math> or <math>9</math> (Because the number of <math>2</math>s in the summation is clearly greater than <math>1000</math>, dividing by <math>10</math> will yield a number greater than <math>100</math>, and multiplying this number by any odd number greater than <math>9</math> will yield an answer <math>>999</math>, which cannot happen on the AIME.) Once you calculate the value of <math>4010</math>, and divide by <math>10</math>, <math>b</math> must be equal to <math>1</math>, as any other value of <math>b</math> will result in an answer <math>>999</math>. This gives <math>\boxed{401}</math> as the answer. | Additionally, once you count the number of factors of <math>2</math> in the summation, one can consider the fact that, since <math>b</math> must be odd, it has to take on a value of <math>1,3,5,7,</math> or <math>9</math> (Because the number of <math>2</math>s in the summation is clearly greater than <math>1000</math>, dividing by <math>10</math> will yield a number greater than <math>100</math>, and multiplying this number by any odd number greater than <math>9</math> will yield an answer <math>>999</math>, which cannot happen on the AIME.) Once you calculate the value of <math>4010</math>, and divide by <math>10</math>, <math>b</math> must be equal to <math>1</math>, as any other value of <math>b</math> will result in an answer <math>>999</math>. This gives <math>\boxed{401}</math> as the answer. | ||
+ | |||
+ | ==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>. | ||
== See Also == | == See Also == |
Revision as of 14:24, 18 June 2017
Contents
Problem
Define to be for odd and for even. When is expressed as a fraction in lowest terms, its denominator is with odd. Find .
Solution 1
First, note that , and that .
We can now take the fraction and multiply both the numerator and the denominator by . We get that this fraction is equal to .
Now we can recognize that is simply , hence this fraction is , and our sum turns into .
Let . Obviously is an integer, and can be written as . Hence if is expressed as a fraction in lowest terms, its denominator will be of the form for some .
In other words, we just showed that . To determine , we need to determine the largest power of that divides .
Let be the largest such that that divides .
We can now return to the observation that . Together with the obvious fact that is odd, we get that .
It immediately follows that , and hence .
Obviously, for the function is is a strictly decreasing function. Therefore .
We can now compute . Hence .
And thus we have , and the answer is .
Additionally, once you count the number of factors of in the summation, one can consider the fact that, since must be odd, it has to take on a value of or (Because the number of s in the summation is clearly greater than , dividing by will yield a number greater than , and multiplying this number by any odd number greater than will yield an answer , which cannot happen on the AIME.) Once you calculate the value of , and divide by , must be equal to , as any other value of will result in an answer . This gives as the answer.
Solution 2
Using the steps of the previous solution we get and if you do the small cases(like ) you realize that youu can "thin-slice" the problem and simply look at the cases where (they're nearly identical in nature but one has with it) since hardly contains any powers of 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 in and and you get the minimum power of in either expression is so the answer is since it would violate the rules of the AIME and the small cases if .
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.