|
問題197（某サイト問）
どのようなn個の整数の組み合わせでも、その中から、合計が18で割り切れるような18個の数を選ぶことができる。そのようなnの最小値をみつけてください。
解答
・わたしの
一般に、
n個の自然数a1,a2,..,anからなる集合Sが与えられているとき、Sのある部分集合でその要素の和がnで割り切れるものが存在する。
（S自身も部分集合に含まれる）
なぜなら、
S1=a1
S2=a1+a2
・
・
・
Sn=a1+a2+・・・+an とおき、
Skをnで割った余りをrkとする。
rkはo〜n-1のn種類だから、
S1〜Sn のなかには rk=0 のものが必ず存在する。
つまり、１８個の数があればかならず１８で割り切れる。
だから、０以外が１７個と、０が１７個のときは無理だが、もう一つ加われば、よいことがわかる。
・風あざみさんのもの Orz〜
問題を一般化して、
n個の整数から、和がmで割り切れるm個の整数を取ることが出来る ⇔ n≧2*m-1･･･※
を示す。(m、nは自然数)
定理１
2m-1個の整数の集合には、和がmで割り切れるようなm個の整数が必ず存在すること。
x_1，x_2，････，x_(2m-1)を0≦x_1≦x_2≦･･･≦x_(2*m-1)なる、整数とする。
ここでは、剰余を問題とするので、0≦x_1≦x_2≦･･･≦x_(2*m-1)＜mと考えて良い。
ここで、補題を示す。
mが素数のとき、定理１は正しい。
証明
整数列y_i（1≦i≦m-1）を、y_i=x_(i+m)-x_iと定義する。
ある値iに対して、y_i=0となったと仮定する。
このとき、x_i=x_(i+1)=･･･=x_(i+m)となる。
このとき、x_i，x_(i+1)，････，x_(i+m-1)が求めるm個の数である。
任意のiに対して、y_i≠0となるとき
0＜y_i＜mとなる。
ここで、整数の集合S_0，S_t(ただし、tは1以上m以下の自然数)，R_tをこう定義する。
S_0={0}
S_t={f_1*y_1+f_2*y_2+･･･+f_t*y_t|f_1,････f_tは0あるいは1}
R_t={s+y_t| sはS_(t-1)の元}
明らかに、S_(t+1)=(S_t)∪{R_(t+1)}である。
ここで、S_tのmod mでの、S_tの元の個数をk個とすると、
k＜mのとき、mod mでの、S_(t+1)の元の個数はk+1個以上となることを示す。･･･☆
S_t={s_1,････,s_k}とおくと、R_(t+1)={s_1+y_(t+1),････,s_k+y_(t+1)}
R_tの任意の元の和を取ると、s_1+･･･+s_k+k*y_(t+1)
S_tの任意の元の和を取ると、s_1+･･･+s_k
mは素数だから、k*y_(t+1)はmでは割り切れない。よって、R_(t+1)には、mod mでS_tのどの元とも等しくない元が存在する。
よって、☆は示された。
また、k=mのとき、S_tは、mod mでの任意の元を含むから、
S_(t+1)=(S_t)∪{R_(t+1)}=S_tとなる。･･･★
☆とS_0={0}より、k＜mのとき、S_kの元の個数≧k+1がわかる。
よって、S_(m-1)の元の個数=mとなる。
S_(m-1)は、mod mでの任意の元を含むから、
x_1+･･･+x_m+f_1*y_1+･･･+f_(m-1)*y_(m-1)がmで割り切れるように、f_1,･･･f_(m-1)を選ぶことが出来る(ただし、f_1,･･･f_(m-1)の値は、0あるいは1)。
x_i+f_i*y_i=x_i あるいは x_(i+m)だから、x_1+･･･+x_m+f_1*y_1+･･･+f_(m-1)*y_(m-1)が求める、m個の数字の和となる。
証明終
本題
定理１は正しい。
証明
数学的帰納法による。
m=1のとき、明らか。
m≦h-1（hは自然数）のとき、正しいと仮定する。
m=hのとき
hが素数のとき、補題より正しい。
hが合成数のとき、
h=a*bとかける
2*a*b-1＞2*a-1
帰納法の仮定より、和がaで割り切れる、a個の整数の集合が存在する。
この集合をT_1とする。
そして、T_1の元を取り除いたa*(2*b-1)-1個の整数で、a*(2*b-1)-1＞2*a-1より、再び和がaで割り切れる、a個の整数の集合が存在する。
この集合をT_2とする。
そして再び、T_2の元を取り除いたa*(2*b-2)-1個の整数で、a*(2*b-2)-1＞2*a-1より、三度和がaで割り切れるa個の整数の集合が存在する。
この集合をT_3とする。
この作業を繰り返すと、和がaで割り切れるようなa個の整数の集合T_jが2*b-1組取ることが出来る。
T_1の元の和，T_2の元の和，･･･，T_(2*b-1)の元の和をそれぞれ、a*w_1,a*w_2,･･･,a*w_(2*b-1)とすると帰納法の仮定より、w_1,･･･,w_(2*b-1)のなかで、bで割り切れるb個の整数が存在する。
これを、w_(i_1),････,w_(i_b)とする。
a*{w_(i_1)+････+w_(i_b)}はa*bで割り切れる。
a*w_(i_1),･･･,a*w_(i_b)は、a個の整数の和である。
しかもこの整数は、x_1,･･･,x_(2*h-1)から取ったものである。
よって、a*{w_(i_1)+････+w_(i_b)}は、x_1,･･･,x_(2*h-1)から取ったh個の整数の和である。
よって、hが合成数のときも定理１は正しい
m=hのときも、定理１は正しいことが示された。
よって、帰納法により任意の自然数mに対して、定理１は正しい。
証明終
定理２
集合{0,････,0(m-1個),1,･･･,1(m-1個)}からは、和がmで割り切れるm個の整数を選ぶことが出来ない。
証明
m個取るのだから、少なくとも、1個は1を取らなければならない。
よって、求める和は少なくとも1以上である。
しかも、1は最大m-1個しかないので、求める和は最大でもm-1以下である。
証明終
定理１と定理２より、※は示された。
|
コメント（2）
