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

Revision as of 12:46, 4 June 2019

Problem

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

Solution

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 \cup \{7\}$ , is $7$ . This is because, since $7$ is the largest element, when we take an alternating sum, each number in $S$ ends up with the opposite sign of each corresponding element of $S\cup \{7\}$ .

Because there are $2^{6} - 1 = 63$ of these pairs of sets (subtracting $1$ to exclude the empty set), the sum of all possible subsets of our given set is $63 \cdot 7$ . However, we forgot to include the subset that only contains $7$ , so the answer is $64 \cdot 7=\boxed{448}$ .

Note: The empty set is the same as the subset that only includes $7$ so you could have just left it as $2^{6}$ pairs of sets.

Solution 2 (almost the same as Solution 1)

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 elements . Since each element of $T'$ has one fewer element preceding it than it does in $T$ , their signs are opposite. Thus 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}$ .

Solution 3

Denote the desired total of all alternating sums of an $n$ -element set as $S_n$ . We are looking for $S_7$ . Notice that all alternating sums of an $n$ -element set are also alternating sums of an $n+1$ -element set. However, when we go from an $n$ to $n+1$ element set, for each subset with the new element, we are adding the new element and subtracting one of the alternating sums of the $n$ -element set. There are $2^n$ subsets of an $n+1$ -element set that includes the new element, giving us the relationship $S_{n+1} = S_n + 2^n(n+1) - S_n = 2^n(n+1)$ . When $n = 6$ , we therefore get $S_ 7 = 2^6(7) = \boxed{448}$ .

@@ Line 10: / Line 10: @@
 Because there are <math>2^{6} - 1 = 63</math> of these pairs of sets (subtracting <math>1</math> to exclude the empty set), the sum of all possible subsets of our given set is <math>63 \cdot 7</math>. However, we forgot to include the subset that only contains <math>7</math>, so the answer is <math>64 \cdot 7=\boxed{448}</math>.
+Note: The empty set is the same as the subset that only includes <math>7</math> so you could have just left it as <math>2^{6}</math> pairs of sets.
 === Solution 2 (almost the same as Solution 1) ===

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

Page

Toolbox

Search