问题及解答

引理. 有 $d$ 个整数 $u_1,u_2,\ldots,u_d$, 则存在 $u_{i_1}+\cdots+u_{i_t}$ $(1\leqslant i_1 < \cdots < i_t\leqslant d)$, 使得 $d|(u_{i_1}+\cdots+u_{i_t})$.

Hint. 使用鸽巢原理.

该引理参见 [1] 中的 Lemma 1.

References:

[1] Norbert Hegyvari, On the representation of integers as sums of distinct terms from a fixed set.  ACTA ARITHMETICA, XCII.2 (2000)

可以对 $d=1,2,3$ 进行手工检验, 结果是正确的. 事实上, 可以用鸽巢原理来证明.

考虑 $d$ 个数

\[
\sum_{j=1}^{k}u_j,\quad k=1,2,\ldots,d.
\]

即

\[
\begin{aligned}
u_1,\\
u_1+u_2,\\
u_1+u_2+u_3,\\
\vdots\\
u_1+u_2+u_3+\cdots+u_d,\\
\end{aligned}
\]

要么存在某个 $k$, 使得 $d|(u_1+u_2+\cdots+u_k)$; 要么所有的数 $\sum_{j=1}^{k}u_j$ 都不能被 $d$ 整除. 对于后者, 这 $n$ 个数中存在两个数, 它们模 $d$ 是相同的. 即存在 $1\leqslant k < m\leqslant d$, 使得

\[
u_1+u_2+\cdots+u_k\equiv u_1+u_2+\cdots+u_m\pmod d
\]

此即 $d|(u_{k+1}+u_{k+2}+\cdots+u_m)$. 证毕.