MathLabs

第6問

m≥2m\ge2 を整数とし、AA を(正とは限らない)整数からなる有限集合、B1,B2,B3,…,BmB_1,B_2,B_3,\ldots,B_m を AA の部分集合とする。すべての k=1,2,…,mk=1,2,\ldots,m について BkB_k の元の和が mkm^k であるとする。AA が少なくとも m/2m/2 個の元を含むことを証明せよ。
ステップ 2/6: AA の元にわたる和として並べ替える
X=∑a∈Afa(X) a,fa(X)=∑i: a∈BiciX=\sum_{a\in A}f_a(X)\,a,\quad f_a(X)=\sum_{i:\,a\in B_i}c_i
詳しい解説

mi=∑b∈Bibm^i=\sum_{b\in B_i}b を代入し和の順序を入れ替えると、X=∑i=1mci∑b∈Bib=∑a∈A(∑i: a∈Bici)a=∑a∈Afa(X) aX=\sum_{i=1}^m c_i\sum_{b\in B_i}b=\sum_{a\in A}\Big(\sum_{i:\,a\in B_i}c_i\Big)a=\sum_{a\in A}f_a(X)\,a となる。ここで fa(X):=∑i: a∈Bicif_a(X):=\sum_{i:\,a\in B_i}c_i である。