Question

令 $S = \{2^0, 2^1, 2^2, \ldots, 2^{10}\}$ 。考虑 $S$ 中两两元素的所有正差。令 $N$ 为所有这些差的和。求 $N$ 除以 $1000$ 的余数。

Let $S = \{2^0, 2^1, 2^2, \ldots, 2^{10}\}.$ Consider all possible positive differences of pairs of elements of $S.$ Let $N$ be the sum of all of these differences. Find the remainder when $N$ is divided by $1000.$

答案

答案：398

知识点：求和 2的幂配对与分组

难度评级：2560

小提示：

在所有正差的和中，数出每个 $2^k$ 被加了多少次、被减了多少次。

In the sum of all positive differences, count how many times each $2^k$ is added and how many times it is subtracted

大提示：

$N = \sum_{k=0}^{10}(2k - 10)\,2^k$ ；用 $\sum k\,2^k$ 和等比数列求值，再模 $1000$ 。

$N = \sum_{k=0}^{10}(2k - 10)\,2^k;$ evaluate with $\sum k\,2^k$ and a geometric series, then reduce mod $1000$

解答：

在所有正差的和中，元素 $2^k$ 会对每个更小的元素被加一次（共 $k$ 次），并对每个更大的元素被减一次（共 $10 - k$ 次）。因此 $\begin{aligned} N &= \sum_{k=0}^{10} (2k - 10)\,2^k \\ &= 2\sum_{k=0}^{10} k\,2^k - 10\sum_{k=0}^{10} 2^k \end{aligned}\text{。}$

标准求和为 $\sum_{k=0}^{10} k\,2^k = 9 \cdot 2^{11} + 2 = 18434$ ，以及 $\sum_{k=0}^{10} 2^k = 2^{11} - 1 = 2047$ ，所以 $\begin{aligned} N &= 2 \cdot 18434 - 10 \cdot 2047 \\ &= 36868 - 20470 = 16398 \end{aligned}\text{。}$

除以 $1000$ 的余数是 $398$ 。

In the sum of all positive differences, the element $2^k$ is added once for each smaller element ( $k$ times) and subtracted once for each larger element ( $10 - k$ times). Hence $\begin{aligned} N &= \sum_{k=0}^{10} (2k - 10)\,2^k \\ &= 2\sum_{k=0}^{10} k\,2^k - 10\sum_{k=0}^{10} 2^k. \end{aligned}$

The standard sums are $\sum_{k=0}^{10} k\,2^k = 9 \cdot 2^{11} + 2 = 18434$ and $\sum_{k=0}^{10} 2^k = 2^{11} - 1 = 2047,$ so $\begin{aligned} N &= 2 \cdot 18434 - 10 \cdot 2047 \\ &= 36868 - 20470 = 16398. \end{aligned}$

The remainder upon division by $1000$ is $398.$

2009 AIME I 第 8 题

答案：398

难度评级：2560

小提示：

大提示：

解答：

其他年份的第 8 题