设 $p$ 是一个奇质数，考虑集合 $\{1,2,\cdots,2p\}$ 的满足以下两条件的子集 $A$：
（1）$A$ 恰有 $p$ 个元素；
（2）$A$ 中所有元素之和可被 $p$ 整除．
试求所有这样的子集 $A$ 的个数．（波兰）
（1）$A$ 恰有 $p$ 个元素；
（2）$A$ 中所有元素之和可被 $p$ 整除．
试求所有这样的子集 $A$ 的个数．（波兰）
【难度】
【出处】
1995年第36届IMO试题
【标注】
【答案】
略
【解析】
记 $U=\{1,2,\cdots,2p\},V=\{p+1,p+2,\cdots,2p\}$，则 $U,V$ 是满足题意的两个子集．
记 $W=\{1,2,\cdots,2p\}$，则 $W$ 共有 $C_{2p}^p$ 个 $p$ 元子集，除去集 $U,V$ 外，$W$ 的每一个 $p$ 元子集都与 $U,V$ 的交为非空，将这些子集分类：设 $S,T$ 是 $W$ 的两个除 $U,V$ 外的 $p$ 元子集，且满足
（1）$S\bigcap =T\bigcap V$；
（2）只要适当编号，$S\bigcap U$ 的元素 $s_1,s_2,\cdots,s_m$ 和 $T\bigcap U$ 的元素 $t_1,t_2,\cdots,t_m$ 对适当的 $k\in\{0,1,2,\cdots,p-1\}$ 满足同余式组 $s_i-t_i\equiv k\pmod{p},i=1,2,\cdots,m$，那么就将 $S$ 和 $T$ 归入同一类．
对于集 $\{0,1,2,\cdots,p-1\}$ 中不同的 $k_1,k_2$，由 $S$ 得到的集为 $T_1,T_2$，元素和的差为 $\sum_{i=1}^ps_i-\sum_{i=1}^pt_i\equiv (k_1-k_2)m\pmod{p}$
其中 $m$ 是 $S\bigcap U$ 的元素个数．由于 $S\bigcap U\ne\varnothing$，所以 $0<m<p$，从而 $(k_1-k_2)m\not\equiv 0\pmod{p}$，即 $T_1\ne T_2$．因此，每一类中恰好有 $p$ 个集，并且这些集的元素之和模 $p$ 各不相同，因而每一类恰有一个满足条件（2）．
综上所述，在 $W=\{1,2,\cdots,2p\}$ 的 $C_{2p}^p$ 个 $p$ 元子集中，除 $U$ 和 $V$ 外，每 $p$ 个子集分成一类，每类中恰有一个子集满足（2），所以，$W=\{1,2,\cdots,2p\}$ 的满足（1）（2）的子集的总数为 $\dfrac{1}{p}(C_{2p}^p-2)+2$．
记 $W=\{1,2,\cdots,2p\}$，则 $W$ 共有 $C_{2p}^p$ 个 $p$ 元子集，除去集 $U,V$ 外，$W$ 的每一个 $p$ 元子集都与 $U,V$ 的交为非空，将这些子集分类：设 $S,T$ 是 $W$ 的两个除 $U,V$ 外的 $p$ 元子集，且满足
（1）$S\bigcap =T\bigcap V$；
（2）只要适当编号，$S\bigcap U$ 的元素 $s_1,s_2,\cdots,s_m$ 和 $T\bigcap U$ 的元素 $t_1,t_2,\cdots,t_m$ 对适当的 $k\in\{0,1,2,\cdots,p-1\}$ 满足同余式组 $s_i-t_i\equiv k\pmod{p},i=1,2,\cdots,m$，那么就将 $S$ 和 $T$ 归入同一类．
对于集 $\{0,1,2,\cdots,p-1\}$ 中不同的 $k_1,k_2$，由 $S$ 得到的集为 $T_1,T_2$，元素和的差为 $\sum_{i=1}^ps_i-\sum_{i=1}^pt_i\equiv (k_1-k_2)m\pmod{p}$
其中 $m$ 是 $S\bigcap U$ 的元素个数．由于 $S\bigcap U\ne\varnothing$，所以 $0<m<p$，从而 $(k_1-k_2)m\not\equiv 0\pmod{p}$，即 $T_1\ne T_2$．因此，每一类中恰好有 $p$ 个集，并且这些集的元素之和模 $p$ 各不相同，因而每一类恰有一个满足条件（2）．
综上所述，在 $W=\{1,2,\cdots,2p\}$ 的 $C_{2p}^p$ 个 $p$ 元子集中，除 $U$ 和 $V$ 外，每 $p$ 个子集分成一类，每类中恰有一个子集满足（2），所以，$W=\{1,2,\cdots,2p\}$ 的满足（1）（2）的子集的总数为 $\dfrac{1}{p}(C_{2p}^p-2)+2$．
答案
解析
备注
