Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 13"
(→Solution) |
|||
Line 6: | Line 6: | ||
Determine the remainder obtained when <math>S</math> is divided by <math>1000</math>. | Determine the remainder obtained when <math>S</math> is divided by <math>1000</math>. | ||
− | ==Solution== | + | ==Solution 1== |
Let <math>S = \sum_{k = 0}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k} = \sum_{k = 1}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k}</math>. Let <math>W = \left(\dfrac{2}{3}\right)^{2005}S</math>. Then note that <math>(x + 1)^{2005} = \sum_{k = 0}^{2005} {2005 \choose k}x^k</math>, so taking the derivative and multiplying by <math>x</math> gives <math>2005x(x + 1)^{2004} = \sum_{k = 0}^{2005} k{2005 \choose k}x^k</math>. Taking the derivative and multiplying by <math>x</math> again gives <math>f(x) = 2005x(x + 1)^{2004} + (2005)(2004)x^2(x + 1)^{2003} = \sum_{k = 0}^{2005} k^2{2005 \choose k}x^k</math>. Now note that <math>f\left(\dfrac{1}{2}\right) = S</math>. Then we get <math>W = \left(\dfrac{2}{3}\right)^{2005}S = \left(\dfrac{2}{3}\right)^{2005}\left(\dfrac{2005}{2}\left(\dfrac{3}{2}\right)^{2004} + (501)(2005)\left(\dfrac{3}{2}\right)^{2003}\right)</math>, so <math>W = \dfrac{2}{3}\cdot\dfrac{2005}{2} + \dfrac{668}{3}\cdot(2005) = 447115</math>, so <math>W \equiv \boxed{115} \pmod{1000}</math>. | Let <math>S = \sum_{k = 0}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k} = \sum_{k = 1}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k}</math>. Let <math>W = \left(\dfrac{2}{3}\right)^{2005}S</math>. Then note that <math>(x + 1)^{2005} = \sum_{k = 0}^{2005} {2005 \choose k}x^k</math>, so taking the derivative and multiplying by <math>x</math> gives <math>2005x(x + 1)^{2004} = \sum_{k = 0}^{2005} k{2005 \choose k}x^k</math>. Taking the derivative and multiplying by <math>x</math> again gives <math>f(x) = 2005x(x + 1)^{2004} + (2005)(2004)x^2(x + 1)^{2003} = \sum_{k = 0}^{2005} k^2{2005 \choose k}x^k</math>. Now note that <math>f\left(\dfrac{1}{2}\right) = S</math>. Then we get <math>W = \left(\dfrac{2}{3}\right)^{2005}S = \left(\dfrac{2}{3}\right)^{2005}\left(\dfrac{2005}{2}\left(\dfrac{3}{2}\right)^{2004} + (501)(2005)\left(\dfrac{3}{2}\right)^{2003}\right)</math>, so <math>W = \dfrac{2}{3}\cdot\dfrac{2005}{2} + \dfrac{668}{3}\cdot(2005) = 447115</math>, so <math>W \equiv \boxed{115} \pmod{1000}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | Let the wanted sum be <math>S</math>. | ||
+ | We will simplify the expression into: <cmath>3^{2005}S = \sum_{k=1}^{2005}2^{2005-k}k^2\dbinom{2005}{k}</cmath>. | ||
+ | A counting argument will be provided to compute this. | ||
+ | |||
+ | Consider <math>2005</math> people, who will be separated into group <math>1</math>, group <math>2</math>, and group <math>3</math>. Furthermore, one person in group <math>1</math> will be cool, and one person will be smart. (They may be the same people). | ||
+ | |||
+ | Consider only putting <math>k</math> people into group <math>1</math>. There are <math>\dbinom{2005}{k}</math> ways this can be done. For the remaining <math>2005-k</math> people, there are one of two groups they can be in, namely group <math>2</math> and group <math>3</math>. This means that there are <math>2^{2005-k}</math> ways this can be done. There are <math>k</math> ways to determine who is cool, and <math>k</math> ways to determine who is cool. This is <math>k^2</math>. As <math>k</math> ranges from <math>1</math> to <math>2005</math>, we will get all such scenarios. This means that the number of ways that this can be done is also <math>3^{2005}S</math>. | ||
+ | |||
+ | Another way to count this is two split it up into two cases. | ||
+ | |||
+ | Case 1: <math>1</math> person is both cool and smart. | ||
+ | There are <math>2005</math> ways to choose this person. The remaining <math>2004</math> people have a choice of one of <math>3</math> groups, making <math>2005 \cdot 3^{2004}</math> ways. | ||
+ | |||
+ | Case 2: <math>1</math> person is cool, and another person in smart. | ||
+ | There are <math>2005</math> ways to choose who is cool, and <math>2004</math> ways to choose who is smart. The remaining <math>2003</math> people have a choice of one of <math>3</math> groups, making <math>2005 \cdot 2004 \cdot 3^{2003}</math>. | ||
+ | |||
+ | |||
+ | Thus, we have: <cmath>3^{2005}S=2005 \cdot 3^{2003}(3+2004) \implies S=2005 \cdot \dfrac{2007}{9}=2005 \cdot 223 \equiv 115 (\text{mod} \ 1000)</cmath> | ||
+ | |||
+ | Thus, the answer is <math>\boxed{115}</math> | ||
==See Also== | ==See Also== | ||
{{Mock AIME box|year=Pre 2005|n=3|num-b=12|num-a=14}} | {{Mock AIME box|year=Pre 2005|n=3|num-b=12|num-a=14}} |
Revision as of 19:36, 26 February 2019
Contents
[hide]Problem
Let denote the value of the sum
Determine the remainder obtained when is divided by .
Solution 1
Let . Let . Then note that , so taking the derivative and multiplying by gives . Taking the derivative and multiplying by again gives . Now note that . Then we get , so , so .
Solution 2
Let the wanted sum be . We will simplify the expression into: . A counting argument will be provided to compute this.
Consider people, who will be separated into group , group , and group . Furthermore, one person in group will be cool, and one person will be smart. (They may be the same people).
Consider only putting people into group . There are ways this can be done. For the remaining people, there are one of two groups they can be in, namely group and group . This means that there are ways this can be done. There are ways to determine who is cool, and ways to determine who is cool. This is . As ranges from to , we will get all such scenarios. This means that the number of ways that this can be done is also .
Another way to count this is two split it up into two cases.
Case 1: person is both cool and smart. There are ways to choose this person. The remaining people have a choice of one of groups, making ways.
Case 2: person is cool, and another person in smart. There are ways to choose who is cool, and ways to choose who is smart. The remaining people have a choice of one of groups, making .
Thus, we have:
Thus, the answer is
See Also
Mock AIME 3 Pre 2005 (Problems, Source) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |