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

 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
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, 3, 6,9\}</math> is <math>9-6+3-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 ==
 +
Let <math>S</math> be a non-empty [[subset]] of <math>\{1,2,3,4,5,6\}</math>.
 +
 +
Then the alternating sum of <math>S</math> plus the alternating sum of <math>S</math> with 7 included is 7. In mathematical terms, <math>S+ (S\cup 7)=7</math>. This is true because when we take an alternating sum, each term of <math>S</math> has the opposite sign of each corresponding term of <math>S\cup 7</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=448</math>.
 +
 +
----
 +
 +
* [[1983 AIME Problems/Problem 12|Previous Problem]]
 +
* [[1983 AIME Problems/Problem 14|Next Problem]]
 +
* [[1983 AIME Problems|Back to Exam]]
  
 
== See also ==
 
== See also ==
* [[1983 AIME Problems]]
+
* [[AIME Problems and Solutions]]
 +
* [[American Invitational Mathematics Examination]]
 +
* [[Mathematics competition resources]]
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 23:20, 23 July 2006

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, 3, 6,9\}$ is $9-6+3-2+1=6$ and for $\{5\}$ it is simply $5$. Find the sum of all such alternating sums for $n=7$.

Solution

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=448$.


See also