Problem:
For and each of its nonempty subsets a unique alternating 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 is and for it is simply .) Find the sum of all such alternating sums for .
Solution:
It is easier, perhaps, to generalize the problem (ever so slightly) by considering the alternating sums for all subsets of , that is, by including the empty set. To include the empty set without affecting the answer we have only to declare that its alternating sum be . The subsets of may be divided into two kinds: those that do not contain and those that do. Moreover, each subset of the first kind may be paired - in a one-to-one correspondence with a subset of the second kind as follows:
(For the empty set we have the correspondence . Then, assuming , the sum of the alternating sums for each such pair of subsets is given by
And since there are such pairs of subsets (why?), the required sum is . Finally, taking . we obtain .
The problems on this page are the property of the MAA's American Mathematics Competitions