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 個の元を含むことを証明せよ。
ステップ 1/6: mm の倍数を mm 進法で表す
前のステップ次のステップ
ざっくり言うと

mm+1m^{m+1} 未満の mm の倍数を mm で割った商は、mm 個の mm 進法の桁に収まる。

X=∑i=1mcimi,ci∈{0,1,…,m−1}X=\sum_{i=1}^m c_i m^i,\quad c_i\in\{0,1,\ldots,m-1\}
詳しい解説

0≤X<mm+10\le X<m^{m+1} が mm の倍数ならば X/m<mmX/m<m^m であるから、X/mX/m は高々 mm 桁の mm 進展開を持ち、X=∑i=1mcimiX=\sum_{i=1}^m c_im^i（各桁 ci∈{0,1,…,m−1}c_i\in\{0,1,\ldots,m-1\}）と書ける。