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 "1998 AIME Problems/Problem 13"

m (randomly seeding \displaystyle to get rid of "failed to parsE")
m (→‎Solution: minor)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
We note that the number of subsets (for now, including the empty subset) with <math>9</math> in it is equal to the number of subsets without a <math>9</math>. To easily see this, take all possible subsets of <math>\displaystyle \{1,2,\ldots,8\}</math>. Since the sets are ordered, a <math>9</math> must go at the end; hence we can just append a <math>9</math> to any of those subsets to get a new one.  
+
We note that the number of subsets (for now, including the empty subset, which we will just define to have a power sum of zero) with <math>9</math> in it is equal to the number of subsets without a <math>9</math>. To easily see this, take all possible subsets of <math>\displaystyle \{1,2,\ldots,8\}</math>. Since the sets are ordered, a <math>9</math> must go at the end; hence we can just append a <math>9</math> to any of those subsets to get a new one.  
  
 
Now that we have drawn that [[bijection]], we can calculate the complex power sum recursively. Since appending a <math>9</math> to a subset doesn't change anything about that subset's complex power sum besides adding an additional term, we have that <math>S_9 = 2S_8 + T_9</math>, where <math>T_9</math> refers to the sum of all of the <math>9i^x</math>.  
 
Now that we have drawn that [[bijection]], we can calculate the complex power sum recursively. Since appending a <math>9</math> to a subset doesn't change anything about that subset's complex power sum besides adding an additional term, we have that <math>S_9 = 2S_8 + T_9</math>, where <math>T_9</math> refers to the sum of all of the <math>9i^x</math>.  
  
−
It a subset of size 1 has a 9, then its power sum must be <math>9i</math>, and there is only <math>1</math> of these such subsets. There are <math>{8\choose1}</math> with <math>9\cdot i^2</math>, <math>{8\choose2}</math> with <math>9\cdot i^3</math>, and so forth. So <math>T_9 = \displaystyle\sum_{k=0}^{8} 9{8\choose{k}}i^{k+1}</math>. This is exactly the [[binomial expansion]] of <math>9i \cdot (1+i)^8</math>. We can use [[De Moivre's Theorem]] to calculate the power: <math>\sqrt{2}^8\cos{8\cdot45} = 16</math>. Hence <math>T_9 = 16\cdot9i = 144i</math>, and <math>S_9 = 2S_8 + 144i = 2(-176 -64i) + 144i = -352 + 16i</math>. Thus, <math>|p| + |q| = |-352| + |16| = 368</math>.
+
It a subset of size 1 has a 9, then its power sum must be <math>9i</math>, and there is only <math>1</math> of these such subsets. There are <math>{8\choose1}</math> with <math>9\cdot i^2</math>, <math>{8\choose2}</math> with <math>9\cdot i^3</math>, and so forth. So <math>T_9 = \displaystyle\sum_{k=0}^{8} 9{8\choose{k}}i^{k+1}</math>. This is exactly the [[binomial expansion]] of <math>9i \cdot (1+i)^8</math>. We can use [[De Moivre's Theorem]] to calculate the power: <math>(\sqrt{2})^8\cos{8\cdot45} = 16</math>. Hence <math>T_9 = 16\cdot9i = 144i</math>, and <math>S_9 = 2S_8 + 144i = 2(-176 -64i) + 144i = -352 + 16i</math>. Thus, <math>|p| + |q| = |-352| + |16| = 368</math>.
  
 
== See also ==
 
== See also ==

Revision as of 10:31, 9 September 2007

Problem

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

Solution

We note that the number of subsets (for now, including the empty subset, which we will just define to have a power sum of zero) with $9$ in it is equal to the number of subsets without a $9$. To easily see this, take all possible subsets of $\displaystyle \{1,2,\ldots,8\}$. Since the sets are ordered, a $9$ must go at the end; hence we can just append a $9$ to any of those subsets to get a new one.

Now that we have drawn that bijection, we can calculate the complex power sum recursively. Since appending a $9$ to a subset doesn't change anything about that subset's complex power sum besides adding an additional term, we have that $S_9 = 2S_8 + T_9$, where $T_9$ refers to the sum of all of the $9i^x$.

It a subset of size 1 has a 9, then its power sum must be $9i$, and there is only $1$ of these such subsets. There are ${8\choose1}$ with $9\cdot i^2$, ${8\choose2}$ with $9\cdot i^3$, and so forth. So $T_9 = \displaystyle\sum_{k=0}^{8} 9{8\choose{k}}i^{k+1}$. This is exactly the binomial expansion of $9i \cdot (1+i)^8$. We can use De Moivre's Theorem to calculate the power: $(\sqrt{2})^8\cos{8\cdot45} = 16$. Hence $T_9 = 16\cdot9i = 144i$, and $S_9 = 2S_8 + 144i = 2(-176 -64i) + 144i = -352 + 16i$. Thus, $|p| + |q| = |-352| + |16| = 368$.

See also

1998 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_AIME_Problems/Problem_13&oldid=15972"