第4問

正整数

n

b

に対し、

b

未満の相異なる正整数

n

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

U

と

V

について

U

の要素和が

V

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

n

を

b

-判別的という。(a)

8

が

100

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

9

が

100

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

ステップ 4/4: 100未満の条件に矛盾させる

(s_4+\cdots+s_9)-(s_1+s_2+s_3)\ge419,\quad (s_1+s_2+s_3+s_6+s_7+s_8+s_9)-(s_4+s_5)\ge399

詳しい解説

s_3 より大きい元を2,3,4個もつ部分集合を数えると400個なので、もう一つの両端差は少なくとも399。二つの不等式を加えると s_6+s_7+s_8+s_9 は409以上。しかし4数は全て99以下なので和は高々394で矛盾。 (b) が従う。