Difference between revisions of "1983 AIME Problems/Problem 13"

m (removed miscellaneous links)
(Solution)
Line 2: Line 2:
 
For <math>\{1, 2, 3, \ldots, n\}</math> and each of its non-empty subsets, an alternating sum is defined as follows. Arrange the number in the subset in decreasing order and then, beginning with the largest, alternately add and subtract succesive numbers. For example, the alternating sum for <math>\{1, 2, 4, 6,9\}</math> is <math>9-6+4-2+1=6</math> and for <math>\{5\}</math> it is simply <math>5</math>. Find the sum of all such alternating sums for <math>n=7</math>.
 
For <math>\{1, 2, 3, \ldots, n\}</math> and each of its non-empty subsets, an alternating sum is defined as follows. Arrange the number in the subset in decreasing order and then, beginning with the largest, alternately add and subtract succesive numbers. For example, the alternating sum for <math>\{1, 2, 4, 6,9\}</math> is <math>9-6+4-2+1=6</math> and for <math>\{5\}</math> it is simply <math>5</math>. Find the sum of all such alternating sums for <math>n=7</math>.
  
== Solution ==
+
== Solution 1==
 
Let <math>S</math> be a non-[[empty set | empty]] [[subset]] of <math>\{1,2,3,4,5,6\}</math>.  
 
Let <math>S</math> be a non-[[empty set | empty]] [[subset]] of <math>\{1,2,3,4,5,6\}</math>.  
  
Line 8: Line 8:
  
 
Because there are <math>63</math> of these pairs, the sum of all possible subsets of our given set is <math>63*7</math>. However, we forgot to include the subset that only contains <math>7</math>, so our answer is <math>64\cdot 7=\boxed{448}</math>.
 
Because there are <math>63</math> of these pairs, the sum of all possible subsets of our given set is <math>63*7</math>. However, we forgot to include the subset that only contains <math>7</math>, so our answer is <math>64\cdot 7=\boxed{448}</math>.
 +
 +
== Solution 2==
 +
 +
Consider a given subset <math>T</math> of <math>S</math> that contains 7; then there is a subset <math>T'</math> which contains all the elements of <math>T</math> except for 7, and only those. Since each element of <math>T'</math> has one element fewer preceding it than it does in <math>T</math>, their signs are opposite; so the sum of the alternating sums of <math>T</math> and <math>T'</math> is equal to 7. There are <math>2^6</math> subsets containing 7, so our answer is <math>7 * 2^6 = \boxed{448}</math>.
  
 
== See Also ==
 
== See Also ==

Revision as of 19:22, 3 September 2012

Problem

For $\{1, 2, 3, \ldots, n\}$ and each of its non-empty subsets, an alternating sum is defined as follows. Arrange the number in the subset in decreasing order and then, beginning with the largest, alternately add and subtract succesive numbers. For example, the alternating sum for $\{1, 2, 4, 6,9\}$ is $9-6+4-2+1=6$ and for $\{5\}$ it is simply $5$. Find the sum of all such alternating sums for $n=7$.

Solution 1

Let $S$ be a non- empty subset of $\{1,2,3,4,5,6\}$.

Then the alternating sum of $S$ plus the alternating sum of $S$ with 7 included is 7. In mathematical terms, $S+ (S\cup 7)=7$. This is true because when we take an alternating sum, each term of $S$ has the opposite sign of each corresponding term of $S\cup 7$.

Because there are $63$ of these pairs, the sum of all possible subsets of our given set is $63*7$. However, we forgot to include the subset that only contains $7$, so our answer is $64\cdot 7=\boxed{448}$.

Solution 2

Consider a given subset $T$ of $S$ that contains 7; then there is a subset $T'$ which contains all the elements of $T$ except for 7, and only those. Since each element of $T'$ has one element fewer preceding it than it does in $T$, their signs are opposite; so the sum of the alternating sums of $T$ and $T'$ is equal to 7. There are $2^6$ subsets containing 7, so our answer is $7 * 2^6 = \boxed{448}$.

See Also

1983 AIME (ProblemsAnswer KeyResources)
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