整数の問題

質問

この前友人が私に出した問題です。

自然数kに対して、次の条件を満たす自然数nの最小値を求めよ。
「任意のn個の整数において、その中から上手くk個を選べば和をkの倍数にすることができる。」
例)k=2のとき…n=2ならば偶奇が異なるとき条件を満たさず、n=3ならば偶奇が一致する二整数が必ず存在するのでnの最小値は3。

k=5まではn=2k-1という関係になったそうです。kが6以上のときもそうなるのか(その場合は証明可能かどうか)、或いは全く関係の無い値になるのか知りたいのだが何か良いアイデアは無いかと聞かれました。
取り敢えずk=6について調べてみようとしましたが分岐が多いので断念しました(k=5でも結構大変そうですが…)。
良い方法がありましたら教えて下さい。

回答No.3

yoikagari · ベストアンサー

見にくてすみません。

n個の整数から、和がkで割り切れるk個の整数を取ることが出来る ⇔ n≧2*k-1・・・※
を示す。(k、nは自然数)

定理１
2k-1個の整数の集合には、和がkで割り切れるようなk個の整数が必ず存在すること。

x_1，x_2，・・・・，x_(2k-1)を0≦x_1≦x_2≦・・・≦x_(2*k-1)なる、整数とする。

ここでは、剰余を問題とするので、0≦x_1≦x_2≦・・・≦x_(2*k-1)＜kと考えて良い。

ここで、補題を示す。

kが素数のとき、定理１は正しい。

証明

整数列y_i（1≦i≦k-1）を、y_i=x_(i+k)-x_iと定義する。

ある値iに対して、y_i=0となったと仮定する。
このとき、x_i=x_(i+1)=・・・=x_(i+k)となる。
このとき、x_i，x_(i+1)，・・・・，x_(i+k-1)が求めるk個の数である。

任意のiに対して、y_i≠0となるとき

0＜y_i＜kとなる。

ここで、整数の集合S_0，S_t(ただし、tは1以上k以下の自然数)，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 kでの、S_tの元の個数をr個とすると、
t＜kのとき、mod kでの、S_(t+1)の元の個数はr+1個以上となることを示す。・・・☆

S_t={s_1,・・・・,s_r}とおくと、R_(t+1)={s_1+y_(t+1),・・・・,s_r+y_(t+1)}

R_tの任意の元の和を取ると、s_1+・・・+s_r+r*y_(t+1)
S_tの任意の元の和を取ると、s_1+・・・+s_r

kは素数だから、r*y_(t+1)はkでは割り切れない。よって、R_(t+1)には、mod kでS_tのどの元とも等しくない元が存在する。

よって、☆は示された。

また、r=kのとき、S_tは、mod kでの任意の元を含むから、
S_(t+1)=(S_t)∪{R_(t+1)}=S_tとなる。・・・★

☆とS_0={0}より、r＜kのとき、S_rの元の個数≧r+1がわかる。

よって、S_(k-1)の元の個数=kとなる。

S_(k-1)は、mod kでの任意の元を含むから、

x_1+・・・+x_k+f_1*y_1+・・・+f_(k-1)*y_(k-1)がkで割り切れるように、f_1,・・・f_(k-1)を選ぶことが出来る(ただし、f_1,・・・f_(k-1)の値は、0あるいは1)。

x_i+f_i*y_i=x_i あるいは x_(i+k)だから、x_1+・・・+x_k+f_1*y_1+・・・+f_(k-1)*y_(k-1)が求める、k個の数字の和となる。

証明終

本題
定理１は正しい。

証明
数学的帰納法による。

k=1のとき、明らか。

k≦h-1（hは自然数）のとき、正しいと仮定する。

k=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が合成数のときも定理１は正しい

k=hのときも、定理１は正しいことが示された。

よって、帰納法により任意の自然数kに対して、定理１は正しい。

証明終

定理２
集合{0,・・・・,0(k-1個),1,・・・,1(k-1個)}からは、和がkで割り切れるk個の整数を選ぶことが出来ない。

証明

k個取るのだから、少なくとも、1個は1を取らなければならない。
よって、求める和は少なくとも1以上である。
しかも、1は最大k-1個しかないので、求める和は最大でもk-1以下である。

証明終

定理１と定理２より、※は示された。」

お礼

確かに難しいですね。理解するのにかなり時間が掛かってしまいました。でも凄く丁寧な回答で分かり易かったです。
私もこういう問題が解けるように日々精進したいと思います。ありがとうございました。

回答No.2

yoikagari

訂正
1の
「ここで、S_tのmod kでの、S_tの元の個数をk個とすると、
k＜kのとき、mod kでの、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

kは素数だから、k*y_(t+1)はkでは割り切れない。よって、R_(t+1)には、mod kでS_tのどの元とも等しくない元が存在する。よって、☆は示された。

また、k=kのとき、S_tは、mod kでの任意の元を含むから、
S_(t+1)=(S_t)∪{R_(t+1)}=S_tとなる。・・・★

☆とS_0={0}より、k＜kのとき、S_kの元の個数≧k+1がわかる。」
は
「ここで、S_tのmod kでの、S_tの元の個数をr個とすると、
r＜kのとき、mod kでの、S_(t+1)の元の個数はr+1個以上となることを示す。・・・☆

S_t={s_1,・・・・,s_r}とおくと、R_(t+1)={s_1+y_(t+1),・・・・,s_r+y_(t+1)}

R_tの任意の元の和を取ると、s_1+・・・+s_r+r*y_(t+1)
S_tの任意の元の和を取ると、s_1+・・・+s_r

kは素数だから、r*y_(t+1)はkでは割り切れない。よって、R_(t+1)には、mod kでS_tのどの元とも等しくない元が存在する。よって、☆は示された。

また、r=kのとき、S_tは、mod kでの任意の元を含むから、
S_(r+1)=(S_r)∪{R_(r+1)}=S_rとなる。・・・★

☆とS_0={0}より、r＜kのとき、S_rの元の個数≧r+1がわかる。」
の誤りです。

回答No.1

yoikagari

難しいかもしれませんが、証明を書いて置きます。

「n個の整数から、和がkで割り切れるk個の整数を取ることが出来る ⇔ n≧2*k-1・・・※
を示す。(k、nは自然数)

定理１
2k-1個の整数の集合には、和がkで割り切れるようなk個の整数が必ず存在すること。

x_1，x_2，・・・・，x_(2k-1)を0≦x_1≦x_2≦・・・≦x_(2*k-1)なる、整数とする。

ここでは、剰余を問題とするので、0≦x_1≦x_2≦・・・≦x_(2*k-1)＜kと考えて良い。

ここで、補題を示す。

kが素数のとき、定理１は正しい。

証明

整数列y_i（1≦i≦k-1）を、y_i=x_(i+k)-x_iと定義する。

ある値iに対して、y_i=0となったと仮定する。
このとき、x_i=x_(i+1)=・・・=x_(i+k)となる。
このとき、x_i，x_(i+1)，・・・・，x_(i+k-1)が求めるk個の数である。

任意のiに対して、y_i≠0となるとき

0＜y_i＜kとなる。

ここで、整数の集合S_0，S_t(ただし、tは1以上k以下の自然数)，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 kでの、S_tの元の個数をk個とすると、
k＜kのとき、mod kでの、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

kは素数だから、k*y_(t+1)はkでは割り切れない。よって、R_(t+1)には、mod kでS_tのどの元とも等しくない元が存在する。

よって、☆は示された。

また、k=kのとき、S_tは、mod kでの任意の元を含むから、
S_(t+1)=(S_t)∪{R_(t+1)}=S_tとなる。・・・★

☆とS_0={0}より、k＜kのとき、S_kの元の個数≧k+1がわかる。

よって、S_(k-1)の元の個数=kとなる。

S_(k-1)は、mod kでの任意の元を含むから、

x_1+・・・+x_k+f_1*y_1+・・・+f_(k-1)*y_(k-1)がkで割り切れるように、f_1,・・・f_(k-1)を選ぶことが出来る(ただし、f_1,・・・f_(k-1)の値は、0あるいは1)。

x_i+f_i*y_i=x_i あるいは x_(i+k)だから、x_1+・・・+x_k+f_1*y_1+・・・+f_(k-1)*y_(k-1)が求める、k個の数字の和となる。

証明終

本題
定理１は正しい。

証明
数学的帰納法による。

k=1のとき、明らか。

k≦h-1（hは自然数）のとき、正しいと仮定する。

k=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が合成数のときも定理１は正しい

k=hのときも、定理１は正しいことが示された。

よって、帰納法により任意の自然数kに対して、定理１は正しい。

証明終

定理２
集合{0,・・・・,0(k-1個),1,・・・,1(k-1個)}からは、和がkで割り切れるk個の整数を選ぶことが出来ない。

証明

k個取るのだから、少なくとも、1個は1を取らなければならない。
よって、求める和は少なくとも1以上である。
しかも、1は最大k-1個しかないので、求める和は最大でもk-1以下である。

証明終

定理１と定理２より、※は示された。」