第6問

m\ge2

を整数とし、

A

を（正とは限らない）整数からなる有限集合、

B_1,B_2,B_3,\ldots,B_m

を

A

の部分集合とする。すべての

k=1,2,\ldots,m

について

B_k

の元の和が

m^k

であるとする。

A

が少なくとも

m/2

個の元を含むことを証明せよ。

ステップ 6/6:

|A|\ge m/2

を結論する

m^m<m^{2|A|}\ \Rightarrow\ |A|>m/2

詳しい解説

$m(m-1)+1<m^2$ であるから $(m(m-1)+1)^{|A|}<m^{2|A|}$ となり、 $m^m<m^{2|A|}$ 、すなわち $m<2|A|$ 、つまり $|A|>m/2$ が得られる。 $|A|$ は整数なので、特に $|A|\ge m/2$ が従い、求める結論となる。