2007 iTest Problems/Problem 25

Problem

Ted's favorite number is equal to \[1\cdot{2007\choose 1}+2\cdot {2007\choose 2}+3\cdot {2007\choose 3} + \cdots + 2007\cdot {2007 \choose 2007}\]

Find the remainder when Ted’s favorite number is divided by 25.

$\text{(A) } 0\qquad \text{(B) } 1\qquad \text{(C) } 2\qquad \text{(D) } 3\qquad \text{(E) } 4\qquad \text{(F) } 5\qquad \text{(G) } 6\qquad \text{(H) } 7\qquad \text{(I) } 8\qquad$

$\text{(J) } 9\qquad \text{(K) } 10\qquad \text{(L) } 11\qquad \text{(M) } 12\qquad \text{(N) } 13\qquad \text{(O) } 14\qquad \text{(P) } 15\qquad \text{(Q) } 16\qquad$

$\text{(R) } 17\qquad \text{(S) } 18\qquad \text{(T) } 19\qquad \text{(U) } 20\qquad \text{(V) } 21\qquad \text{(W) } 22\qquad \text{(X) } 23\qquad \text{(Y) } 24$

Solution

Let $T = \sum_{i=1}^{2007} i \cdot \binom{2007}{i}$. That means \[2T = 2 \cdot \sum_{i=1}^{2007} (i \cdot \binom{2007}{i}\] We know that $\binom{2007}{i} = \binom{2007}{2007-i}$, so \[2T = \sum_{i=1}^{2007} (i \cdot \binom{2007}{i}) + \sum_{j=1}^{2007} (j \cdot \binom{2007}{2007-j})\] If $2007-j= i$, then $i+j = 2007$, so \[2T = 2007 \cdot \sum_{i=0}^{2007} \binom{2007}{i}\] \[2T = 2007 \cdot 2^{2007}\] \[T = 2007 \cdot 2^{2006}\] Note that $2^{10} \equiv -1 \pmod{25}$. Using the properties of modular arithmetic, we can find the remainder when $T$ is divided by $25$. \[T \equiv 2007 \cdot 2^{2000} \cdot 2^6 \pmod{25}\] \[T \equiv 2007 \cdot (2^{10})^{200} \cdot 64 \pmod{25}\] \[T \equiv 7 \cdot 1 \cdot 14 \pmod{25}\] \[T \equiv 98 \pmod{25}\] \[T \equiv 23 \pmod{25}\] The remainder when Ted’s favorite number is divided by 25 is $\boxed{\textbf{(X) } 23}$.

See Also

2007 iTest (Problems, Answer Key)
Preceded by:
Problem 24
Followed by:
Problem 26
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 TB1 TB2 TB3 TB4