用 $S$ 表示集合 $\left\{ 1,2,3,\cdots,10 \right\}$．设 $n$ 为 $S$ 中非空互斥子集的对数．（互斥集合定义为没有共同元素的两个集合．）试求 $n$ 被1000整除所得的余数．
【难度】
【出处】
2002年第20届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
501
【解析】
设 $k$ 为集合 $S$ 中元素的个数，$A$ 和 $B$ 为两个空罐子，将 $S$ 中的元素装入两个罐子得到两个互斥子集．对于 $S$ 中每个元素 $x$ 都存在三种可能性：放入 $A$，放入 $B$ 或者即不放入 $A$ 也不放入 $B$．因此互斥子集 $\left( A B \right)$ 的对数共有 ${{3}^{k}}$．但有一种情况是，一对中可能 $A$ 或 $B$ 为空．注意到若 $A$ 为空，$S$ 中每个元素 $x$ 存在两种可能性：放入 $B$，不放入 $B$．那么当 $A$ 或 $B$ 为空时对数有 ${{2}^{k}}+{{2}^{k}}-1={{2}^{k+1}}-1$．因为交换 $A$，$B$ 不会产生不同的子集，因此共有 $\frac{1}{2}\left( {{3}^{k}}-{{2}^{k+1}}+1 \right)=\frac{1}{2}\left({{3}^{k}}+1 \right)-{{2}^{k}}$ 对互斥子集．当 $k=10$ 时，$n=\frac{{{3}^{10}}+1}{2}-{{2}^{10}}=28501$，因此余数等于501．
答案
解析
备注
