(NIMO 2014) Sum of Powers of i

Algebra Level 5

Let $S = \left\{ 1,2, \dots, 2014 \right\}$ . Suppose that $\sum_{T \subseteq S} i^{\left\lvert T \right\rvert} = p + qi$ where $p$ and $q$ are integers, $i = \sqrt{-1}$ , and the summation runs over all $2^{2014}$ subsets of $S$ . Find the remainder when $\left\lvert p\right\rvert + \left\lvert q \right\rvert$ is divided by $1000$ . (Here $\left\lvert X \right\rvert$ denotes the number of elements in a set $X$ .)

The answer is 128.

1 solution

David Altizio
Oct 4, 2015

Replace $2014$ with $n$ . For each $1\leq k\leq n$ , there are $\binom nk$ subsets of $S$ with cardinality $k$ . Thus the sum rearranges to $\sum_{k=0}^{n}\dbinom nki^k=(1+i)^n.$ Using Demoivre's or similar on $n=2014$ gives $f(2014)=(\sqrt{2}e^{\pi i/2})^{2014}=-2^{1007}i$ , so $|p|+|q|=2^{1007}$ .

Now use Chinese Remainder Theorem to compute the value of this expression $\pmod{1000}$ . Clearly $2^{1007}\equiv 0\pmod 8$ . To compute the remainder mod $125$ , we use Euler. Since $\phi(125)=100$ , $2^{1007}\equiv 2^7\equiv 128\pmod{125}$ . Now observe that $128\equiv 0\pmod{8}$ as well, so $\boxed{128}$ is the remainder upon division by $1000$ .

(NIMO 2014) Sum of Powers of i

The answer is 128.

1 solution

0 pending reports