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 3 Pre 2005 Problems/Problem 13

Revision as of 19:36, 26 February 2019 by Rd123 (talk | contribs) (→‎Solution)

Problem

$13.$ Let $S$ denote the value of the sum

$\left(\frac{2}{3}\right)^{2005} \cdot \sum_{k=1}^{2005} \frac{k^2}{2^k} \cdot {2005 \choose k}$

Determine the remainder obtained when $S$ is divided by $1000$.

Solution 1

Let $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}$. Let $W = \left(\dfrac{2}{3}\right)^{2005}S$. Then note that $(x + 1)^{2005} = \sum_{k = 0}^{2005} {2005 \choose k}x^k$, so taking the derivative and multiplying by $x$ gives $2005x(x + 1)^{2004} = \sum_{k = 0}^{2005} k{2005 \choose k}x^k$. Taking the derivative and multiplying by $x$ again gives $f(x) = 2005x(x + 1)^{2004} + (2005)(2004)x^2(x + 1)^{2003} = \sum_{k = 0}^{2005} k^2{2005 \choose k}x^k$. Now note that $f\left(\dfrac{1}{2}\right) = S$. Then we get $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)$, so $W = \dfrac{2}{3}\cdot\dfrac{2005}{2} + \dfrac{668}{3}\cdot(2005) = 447115$, so $W \equiv \boxed{115} \pmod{1000}$.

Solution 2

Let the wanted sum be $S$. We will simplify the expression into: \[3^{2005}S = \sum_{k=1}^{2005}2^{2005-k}k^2\dbinom{2005}{k}\]. A counting argument will be provided to compute this.

Consider $2005$ people, who will be separated into group $1$, group $2$, and group $3$. Furthermore, one person in group $1$ will be cool, and one person will be smart. (They may be the same people).

Consider only putting $k$ people into group $1$. There are $\dbinom{2005}{k}$ ways this can be done. For the remaining $2005-k$ people, there are one of two groups they can be in, namely group $2$ and group $3$. This means that there are $2^{2005-k}$ ways this can be done. There are $k$ ways to determine who is cool, and $k$ ways to determine who is cool. This is $k^2$. As $k$ ranges from $1$ to $2005$, we will get all such scenarios. This means that the number of ways that this can be done is also $3^{2005}S$.

Another way to count this is two split it up into two cases.

Case 1: $1$ person is both cool and smart. There are $2005$ ways to choose this person. The remaining $2004$ people have a choice of one of $3$ groups, making $2005 \cdot 3^{2004}$ ways.

Case 2: $1$ person is cool, and another person in smart. There are $2005$ ways to choose who is cool, and $2004$ ways to choose who is smart. The remaining $2003$ people have a choice of one of $3$ groups, making $2005 \cdot 2004 \cdot 3^{2003}$.


Thus, we have: \[3^{2005}S=2005 \cdot 3^{2003}(3+2004) \implies S=2005 \cdot \dfrac{2007}{9}=2005 \cdot 223 \equiv 115 (\text{mod} \ 1000)\]

Thus, the answer is $\boxed{115}$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_3_Pre_2005_Problems/Problem_13&oldid=103880"