第3题

求所有正整数

k

，使得存在正整数

m

与正整数集合

S

，使任意整数

n>m

都恰好能表示成

S

中互不相同元素之和的

k

种方式。

第 5/5 步：按余数计数表示数迫使 k 是二的幂

上一步下一步

\#\{T'\subseteq T: s(T')\equiv y \pmod x\}=k\ \text{ for every residue},\quad kx=2^{|T|}

详细分析

由于一旦是 $x$ 的充分大倍数，任何非负整数都能唯一地表示成 $\{x,2x,4x,\ldots\}$ 中相异元素之和，所以将充分大的 $y$ 表示为 $S$ 中相异元素之和的方式数，等于满足 $s(T')\equiv y\pmod x$ 的子集 $T'\subseteq T$ 的个数。对 $x$ 个剩余类中的每一个，此计数都必须等于 $k$ ，于是 $kx$ 等于 $T$ 的子集总数 $2^{|T|}$ 。因此 $k$ 整除 $2^{|T|}$ ，即 $k$ 是二的幂，分类完成。