2009 AIME I 第 8 题

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;$ evaluate with $\sum k\,2^k$ and a geometric series, then reduce mod $1000$

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