第6题

设

p

为奇素数。集合

\{1,2,\ldots,2p\}

的

p

元子集

A

中，元素之和被

p

整除的有多少个？

第 3/3 步：每轨道计数一个零和子集

上一步下一步

通俗地说

由于 $p$ 为素数且 $r$ 模 $p$ 非零， $p$ 个和恰为全部剩余类。

2+\frac{\binom{2p}{p}-2}{p}

详细分析

所有元素之和在轨道中相邻元素间相差 $r\not\equiv0\pmod p$ ，故 $p$ 个和遍历模 $p$ 的全部剩余类。每个轨道恰有一个总和被整除。非特殊部分贡献 $\frac{\binom{2p}{p}-2}{p}$ ；加上两个被排除的子集得到 $2+\frac{\binom{2p}{p}-2}{p}$ 。