第3問

正整数

m

と正整数からなる集合

S

が存在して、任意の整数

n>m

が

S

の相異なる要素の和としてちょうど

k

通りに書けるような、正整数

k

をすべて求めよ。

ステップ 5/5: 剰余類ごとに表示数を数え k が2のべきであることを強制する

前のステップ次のステップ

\#\{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$ は2のべきとなって分類が完成する。