Question

If $\{a_1, a_2, a_3, \ldots, a_n\}$ is a set of real numbers, indexed so that $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_n,$ its complex power sum is defined to be $a_1 i + a_2 i^2 + a_3 i^3 + \cdots + a_n i^n,$ where $i^2 = -1.$ Let $S_n$ be the sum of the complex power sums of all nonempty subsets of $\{1, 2, \ldots, n\}.$ Given that $S_8 = -176 - 64i$ and $S_9 = p + qi,$ where $p$ and $q$ are integers, find $|p| + |q|.$

Answer

Answer: 368

Concepts:complex number recursion binomial theorem

Difficulty rating: 2920

Solution:

Split the nonempty subsets of $\{1, \ldots, 9\}$ by whether they contain $9.$ Those without $9$ contribute $S_8.$ A subset containing $9$ is $T \cup \{9\}$ for a (possibly empty) $T \subseteq \{1, \ldots, 8\},$ and since $9$ is its largest element, its complex power sum is the complex power sum of $T$ plus $9i^{|T| + 1}.$ Summing over all $T$ gives another $S_8$ plus $\sum_{k=0}^{8} \binom{8}{k}\, 9\, i^{k+1} = 9i\,(1 + i)^8.$

Since $(1 + i)^2 = 2i,$ we get $(1 + i)^8 = (2i)^4 = 16,$ so $\begin{aligned} S_9 &= 2S_8 + 144i \\ &= 2(-176 - 64i) + 144i \\ &= -352 + 16i. \end{aligned}$

Therefore $|p| + |q| = 352 + 16 = 368.$

1998 AIME Problem 13

Answer: 368

Difficulty rating: 2920

Solution:

Problem 13 in Other Years