设 $S=\left\{ {{2}^{0}} ,{{2}^{1}}, {{2}^{1}} ,\ldots ,{{2}^{10}} \right\}$．考虑集合 $S$ 中两个元素所有可能的差的绝对值，记 $N$ 为这些绝对值的和，求 $N$ 除以1000的余数．
【难度】
【出处】
2009年第27届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
398
【解析】
对于 $n\geqslant 1$，用 ${{T}_{n}}$ 来表示集合 $\left\{ {{2}^{0}} ,{{2}^{1}} ,{{2}^{1}}, \ldots ,{{2}^{n}} \right\}$ 中两个元素所有可能的差的绝对值之和．给定这个集合的两个元素，如果它们都不等于 ${{2}^{n}}$，则它们的差是 ${{T}_{n-1}}$ 中的一部分．因此，
${{T}_{n}}={{T}_{n-1}}+\left( {{2}^{n}}-{{2}^{n-1}}\right)+\left( {{2}^{n}}-{{2}^{n-2}} \right)+\ldots +\left( {{2}^{1}}-{{2}^{0}}\right)$
$={{T}_{n-1}}+n\cdot {{2}^{n}}-\left( {{2}^{n}}-1\right)$．
于是，重复运用递推公式可得
$\displaystyle {{T}_{n}}=\sum\limits_{k=1}^{n}{\left( k\cdot{{2}^{k}}-{{2}^{k}}+1 \right)}$
$\displaystyle =\sum\limits_{k=1}^{n}{k\cdot{{2}^{k}}-\sum\limits_{k=1}^{n}{{{2}^{k}}}+\sum\limits_{k=1}^{n}{1}}$
$\displaystyle \text{=}\sum\limits_{k=1}^{n}{k\cdot {{2}^{k}}-\left({{2}^{n+1}}-2 \right)}+n$
$\displaystyle \text{=}\sum\limits_{k=1}^{n}{\left(\sum\limits_{i=k}^{n}{{{2}^{i}}} \right)}-\left( {{2}^{n+1}}-2 \right)+n$
$\displaystyle =\sum\limits_{k=1}^{n}{\frac{{{2}^{k}}\left({{2}^{n-k+1}}+1 \right)}{2-1}-\left( {{2}^{n+1}}-2 \right)+n}$
$\displaystyle =\sum\limits_{k=1}^{n}{\left( {{2}^{n+1}}-{{2}^{k}}\right)-\left( {{2}^{n+1}}-2 \right)+n}$
$=n\cdot {{2}^{n+1}}-\left( {{2}^{n+1}}-2 \right)-\left({{2}^{n+1}}-2 \right)+n$
$=\left( n-2 \right)\cdot {{2}^{n+1}}+n-4$．
当 $n=10$ 时可得 $N={{T}_{10}}={{2}^{14}}+14=16398$，故 $N=398\left(\bmod 1000 \right)$．
${{T}_{n}}={{T}_{n-1}}+\left( {{2}^{n}}-{{2}^{n-1}}\right)+\left( {{2}^{n}}-{{2}^{n-2}} \right)+\ldots +\left( {{2}^{1}}-{{2}^{0}}\right)$
$={{T}_{n-1}}+n\cdot {{2}^{n}}-\left( {{2}^{n}}-1\right)$．
于是，重复运用递推公式可得
$\displaystyle {{T}_{n}}=\sum\limits_{k=1}^{n}{\left( k\cdot{{2}^{k}}-{{2}^{k}}+1 \right)}$
$\displaystyle =\sum\limits_{k=1}^{n}{k\cdot{{2}^{k}}-\sum\limits_{k=1}^{n}{{{2}^{k}}}+\sum\limits_{k=1}^{n}{1}}$
$\displaystyle \text{=}\sum\limits_{k=1}^{n}{k\cdot {{2}^{k}}-\left({{2}^{n+1}}-2 \right)}+n$
$\displaystyle \text{=}\sum\limits_{k=1}^{n}{\left(\sum\limits_{i=k}^{n}{{{2}^{i}}} \right)}-\left( {{2}^{n+1}}-2 \right)+n$
$\displaystyle =\sum\limits_{k=1}^{n}{\frac{{{2}^{k}}\left({{2}^{n-k+1}}+1 \right)}{2-1}-\left( {{2}^{n+1}}-2 \right)+n}$
$\displaystyle =\sum\limits_{k=1}^{n}{\left( {{2}^{n+1}}-{{2}^{k}}\right)-\left( {{2}^{n+1}}-2 \right)+n}$
$=n\cdot {{2}^{n+1}}-\left( {{2}^{n+1}}-2 \right)-\left({{2}^{n+1}}-2 \right)+n$
$=\left( n-2 \right)\cdot {{2}^{n+1}}+n-4$．
当 $n=10$ 时可得 $N={{T}_{10}}={{2}^{14}}+14=16398$，故 $N=398\left(\bmod 1000 \right)$．
答案
解析
备注
