所有子集的“交错和”权重之和

Find the sum of the weights of all the subsets

专题: Discrete Math / 离散数学
难度: L4
来源: QuantQuestion

题目详情

对集合 $\{1,2,3,\dots,2013\}$ 的每个子集，把元素按升序排列并交替加减求和（第一个加、第二个减、第三个加…），得到的整数称为该子集的权重。

求所有子集权重之和。

For every subset of $\{1,2,3,\dots,2013\}$ , arrange the numbers in the increasing order and take the sum with alternating signs. The resulting integer is called the weight of the subset. Find the sum of the weights of all the subsets of $\{1,2,3,\dots,2013\}$ .

解析

把不含 1 的子集 $S$ 与含 1 的子集 $\{1\}\cup S$ 成对。

可验证每一对满足

w(S)+w(\{1\}\cup S)=1.

共有 $2^{2012}$ 对，因此总和为

2^{2012}.

Original Explanation

Let $w(S)$ denote the weight of subset S. Every subset S of $\{1,2,3,\dots,2013\}$ that does not contain element 1 can be uniquely paired with the subset $\{1\} \cup S$ that contains element 1. Since there are $2^{2013}$ subsets of $\{1,2,3,\dots,2013\}$ , there are $2^{2012}$ such pairs. Note that $w(S) + w(\{1\} \cup S) = 1$ ; that is, the combined weight of each pair is 1. For example,

\begin{array}{rlr} & {} & {w(\{2,5,8\}) + w(\{1,2,5,8\})}\\ & = & {(2 - 5 + 8) + (1 - 2 + 5 - 8)}\\ & = & {1.} \end{array}

Hence, the sum of weights of all the subsets is $2^{2012}$ .