1983 AIME Problem 13

Question

For

\{1,2,3,\ldots,n\}

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

\{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.

Answer

Answer: 448

Concepts:subsets double counting binomial theorem

Difficulty rating: 2650

Small hint:

Add the contribution of each number separately over all subsets

Big hint:

The sign of

k

depends only on whether the subset contains an even or odd number of elements greater than

k

Solution:

Fix

k.

Once

k

is included, the

k-1

smaller elements may be chosen arbitrarily, contributing a factor of

2^{k-1}.

If exactly

j

of the

7-k

larger elements are chosen, the sign of

k

is

(-1)^j.

Therefore the coefficient of

k

in the total is

\begin{aligned} &2^{k-1}\sum_{j=0}^{7-k} (-1)^j\binom{7-k}{j}\\ &\qquad=2^{k-1}(1-1)^{7-k}. \end{aligned}

This is

0

for

k<7

and

2^6

for

k=7.

Hence the total is

7\cdot2^6=448.