Difference between revisions of "1983 AIME Problems/Problem 13"
m (fixed typo) |
|||
Line 12: | Line 12: | ||
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>. | 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>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | Denote the desired total of alternating sums of an <math>n</math> element set with <math>S_n</math>. We are looking for <math>S_7</math>. Note that all alternating sums of an <math>n</math> element set are also alternating sums of an <math>n+1</math> element set. However, when we go from an <math>n</math> to <math>n+1</math> element set, for each subset with the new element, we are adding the new element and subtracting one of the alternating sums of the <math>n</math> element set. There are <math>2^n</math> subsets of an <math>n+1</math> element set that includes the new element, giving us the following relationship. | ||
+ | |||
+ | <math>S_{n+1} = S_n + 2^n(n+1) - S^n = 2^n(n+1)</math>. | ||
+ | |||
+ | For <math>n = 6</math>, this becomes <math>S_ 7 = 2^6(7) = \boxed{448}</math>. | ||
== See Also == | == See Also == |
Revision as of 20:58, 31 January 2017
Problem
For 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 successive numbers. For example, the alternating sum for is and for it is simply . Find the sum of all such alternating sums for .
Solution 1
Let be a non- empty subset of .
Then the alternating sum of plus the alternating sum of with 7 included is 7. In mathematical terms, . This is true because when we take an alternating sum, each term of has the opposite sign of each corresponding term of .
Because there are of these pairs, the sum of all possible subsets of our given set is . However, we forgot to include the subset that only contains , so our answer is .
Solution 2
Consider a given subset of that contains 7; then there is a subset which contains all the elements of except for 7, and only those. Since each element of has one element fewer preceding it than it does in , their signs are opposite; so the sum of the alternating sums of and is equal to 7. There are subsets containing 7, so our answer is .
Solution 3
Denote the desired total of alternating sums of an element set with . We are looking for . Note that all alternating sums of an element set are also alternating sums of an element set. However, when we go from an to element set, for each subset with the new element, we are adding the new element and subtracting one of the alternating sums of the element set. There are subsets of an element set that includes the new element, giving us the following relationship.
.
For , this becomes .
See Also
1983 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 |