2007年中国西部数学奥林匹克试题

• 知识点

  >

  二试组合部分

略

对于空集 $\varnothing$，定义 $S(\varnothing)=0$．令 $T_{0}=\{3,6\}, \quad T_{1}=\{1,4,7\}, T_{2}=\{2,5,8\}$．对于 $A \subseteq T$，令 $A_{0}=A \bigcap T_{0},A_{1}=A \cap T_{1},A_{2}=A \cap T_{2}$，则
$S(A)=S\left(A_{0}\right)+S\left(A_{1}\right)+S\left(A_{2}\right) \equiv\left|A_{1}\right|-\left|A_{2}\right|(\bmod 3)$，
因此，$3 | S(A)$ 当且仅当 $\left|A_{1}\right| \equiv\left|A_{2}\right|(\bmod 3)$．有以下几种情况：
$\left\{\begin{array}{l}{\left|A_{1}\right|=0,} \\ {\left|A_{2}\right|=0,}\end{array}\left\{\begin{array}{l}{\left|A_{1}\right|=0,} \\ {\left|A_{2}\right|=3,}\end{array}\left\{\begin{array}{l}{\left|A_{1}\right|=3} \\ {\left|A_{2}\right|=0}\end{array}\right.\right.\right.$
$\left\{\begin{array}{l}{\left|A_{1}\right|=3,} \\ {\left|A_{2}\right|=3,}\end{array}\left\{\begin{array}{l}{\left|A_{1}\right|=1,} \\ {\left|A_{2}\right|=1,}\end{array}\left\{\begin{array}{l}{\left|A_{1}\right|=2} \\ {\left|A_{2}\right|=2}\end{array}\right.\right.\right.$
从而满足 $3|S(A)$ 的非空子集 $A$ 的个数为 $2^{2}\left(\mathrm{C}_{3}^{0} \mathrm{C}_{3}^{0}+\mathrm{C}_{3}^{0} \mathrm{C}_{3}^{3}+\mathrm{C}_{3}^{3} \mathrm{C}_{3}^{0}+\mathrm{C}_{3}^{3} \mathrm{C}_{3}^{3}+\mathrm{C}_{3}^{1} \mathrm{C}_{3}^{1}+\mathrm{C}_{3}^{2} \mathrm{C}_{3}^{2}\right)-1=87$
若 $3|S(A), 5| S(A)$，则 $15 | S(A)$．
由于 $S(T)=36$，故满足 $3|S(A), 5| S(A)$ 的 $S(A)$ 的可能值为 $15,30$．而
$\begin{aligned} 15 &=8+7=8+6+1=8+5+2=8+4+3=8+4+2+1 \\ &=7+6+2=7+5+3=7+5+2+1=7+4+3+1 \\ &=6+5+4=6+5+3+1=6+4+3+2 \\ &=5+4+3+2+1 \\ 36 &-30=6=5+1=4+2=3+2+1 \end{aligned}$
放同时满足 $3|S(A), 5| S(A), A \neq \varnothing$ 的 $A$ 的个数为 $17$．
所以，所求的 $A$ 的个数为 $87-17= 70$．