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 個の元を含むことを証明せよ。
ステップ 3/6: すべての aa、XX に対して fa(X)f_a(X) を評価する
0≤fa(X)≤m(m−1)0\le f_a(X)\le m(m-1)
詳しい解説

fa(X)f_a(X) は高々 mm 個の桁(それぞれ {0,1,…,m−1}\{0,1,\ldots,m-1\} に属する)の和であるから、任意の a∈Aa\in A と mm+1m^{m+1} 未満の任意の mm の倍数 XX に対して 0≤fa(X)≤m(m−1)0\le f_a(X)\le m(m-1) が成り立つ。