第4問

正整数

n

b

に対し、

b

未満の相異なる正整数

n

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

U

と

V

について

U

の要素和が

V

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

n

を

b

-判別的という。(a)

8

が

100

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

9

が

100

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

ステップ 2/4: 部分集合和を数える

63+64+64+64=255=2^8-1

詳しい解説

4つの族は互いに異なる合同類または値域にあり、個数はそれぞれ63,64,64,64。従って255個の和が異なり、これは8元集合の空でない部分集合数に等しい。(a) が示された。