第4問

正整数

n

b

に対し、

b

未満の相異なる正整数

n

個からなる集合で、異なる部分集合

U

と

V

について

U

の要素和が

V

の要素和に等しくならないものが存在するとき、

n

を

b

-判別的という。(a)

8

が

100

-判別的であることを示せ。(b)

9

が

100

-判別的でないことを示せ。

ステップ 1/4: 8元の構成を与える

S=\{3,6,12,24,48,95,96,97\}=\{3\cdot2^k:0\le k\le5\}\cup\{95,96,97\}

詳しい解説

表示の集合を取る。最初の6元の部分集合和は t=1 から63の全ての 3t である。95 と97を両方加えると192にこれらを足した和、片方だけ加えるとそれぞれ3を法として−1、1の和になる。