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

m (→‎Solution 2)
m (→‎Solution 2)
 
Line 16: Line 16:
 
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 <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>.
+
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 smart. 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.
 
Another way to count this is two split it up into two cases.

Latest revision as of 13:53, 19 July 2020

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 smart. 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=128679"