Question

对于 $\{1,2,3,\ldots,n\}$ 的每个非空子集，按以下方法定义一个唯一的交错和：先把子集中的数按递减顺序排列，再从最大的数开始，对后续各数交替做加法和减法。（例如， $\{1,2,4,6,9\}$ 的交错和是 $9-6+4-2+1=6$ ，而 $\{5\}$ 的交错和就是 $5$ 。）求 $n=7$ 时所有这些交错和的总和。

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.$

答案

答案：448

知识点：子集双重计数二项式定理

难度评级：2650

小提示：

在所有子集中，分别计算每个数对总和的贡献

Add the contribution of each number separately over all subsets

大提示：

$k$ 的符号只取决于子集中大于 $k$ 的元素个数是偶数还是奇数

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

解答：

固定 $k$ 。一旦选入 $k$ ，比它小的 $k-1$ 个元素都可以任意选择，因此产生因子 $2^{k-1}$ 。若恰好选入 $j$ 个元素，而可供选择的较大元素共有 $7-k$ 个，则 $k$ 的符号为 $(-1)^j$ 。所以总和中 $k$ 的系数为 $\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}\text{。}$ 该系数等于 $0$ （若 $k<7$ ），并等于 $2^6$ （若 $k=7$ ）。因此总和为 $7\cdot2^6=448$ 。

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.$

1983 AIME 第 13 题

答案：448

难度评级：2650

小提示：

大提示：

解答：

其他年份的第 13 题