问题及解答

设 $p$ 是素数, 则集合 $\{1,2,\ldots,k\}$ 可划分为 $p$ 个子集, 其元素之和都相等的充分必要条件是

\[
k\geqslant 2p-1\quad\text{且}\quad p|\frac{1}{2}k(k+1)
\]

必要性 ($\Rightarrow$)

设 $\{1,2,\ldots,k\}=\cup_{i=1}^{p}S_i$, 这里 $S_i$ 是集合 $\{1,2,\ldots,k\}$ 的子集. 记为 $S_i=\{a_{ij}|j=1,2,\ldots,m_i\}$. 于是

\[
\sum_{j=1}^{m_i}a_{ij}=A,\quad\ i=1,2,\ldots,p.
\]

因此, $pA=1+2+\cdots+k=\frac{1}{2}k(k+1)$, 这推出 $p|\frac{1}{2}k(k+1)$.

另一方面, 由于至少有个子集 $S_{i_0}$ 包含元素 $k$, 故 $A\geqslant k$, 因此 $p\leqslant\frac{k+1}{2}$, 即 $k\geqslant 2p-1$.

注意, 必要性中并不需要 $p$ 是素数这个条件.