第4問

正整数

n

b

に対し、

b

未満の相異なる正整数

n

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

U

と

V

について

U

の要素和が

V

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

n

を

b

-判別的という。(a)

8

が

100

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

9

が

100

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

ステップ 3/4: 最初の鳩の巣計数を行う

\binom93+\binom94+\binom95+\binom96=420

詳しい解説

9元が存在すると仮定し s_1<...<s_9<100 と並べる。3から6元の部分集合は和が全て異なり、最小の3元和と最大の6元和の間にある。420個あるので両端の差は少なくとも419である。