整数の問題
- 自然数kに対して、任意のn個の整数から上手くk個を選べば和をkの倍数にできる自然数nの最小値を求める問題です。
- k=5まではn=2k-1という関係になりますが、kが6以上の場合は関係があるのかどうか、また証明可能かどうかを調査したいとのことです。
- k=6について調べてみましたが、分岐が多くて難しかったため断念しました。良い方法があれば教えてください。
- ベストアンサー
整数の問題
この前友人が私に出した問題です。 自然数kに対して、次の条件を満たす自然数nの最小値を求めよ。 「任意のn個の整数において、その中から上手くk個を選べば和をkの倍数にすることができる。」 例)k=2のとき…n=2ならば偶奇が異なるとき条件を満たさず、n=3ならば偶奇が一致する二整数が必ず存在するのでnの最小値は3。 k=5まではn=2k-1という関係になったそうです。kが6以上のときもそうなるのか(その場合は証明可能かどうか)、或いは全く関係の無い値になるのか知りたいのだが何か良いアイデアは無いかと聞かれました。 取り敢えずk=6について調べてみようとしましたが分岐が多いので断念しました(k=5でも結構大変そうですが…)。 良い方法がありましたら教えて下さい。
- 数学・算数
- 回答数3
- ありがとう数3
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
見にくてすみません。 n個の整数から、和がkで割り切れるk個の整数を取ることが出来る ⇔ n≧2*k-1・・・※ を示す。(k、nは自然数) 定理1 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が素数のとき、定理1は正しい。 証明 整数列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個の数字の和となる。 証明終 本題 定理1は正しい。 証明 数学的帰納法による。 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が合成数のときも定理1は正しい k=hのときも、定理1は正しいことが示された。 よって、帰納法により任意の自然数kに対して、定理1は正しい。 証明終 定理2 集合{0,・・・・,0(k-1個),1,・・・,1(k-1個)}からは、和がkで割り切れるk個の整数を選ぶことが出来ない。 証明 k個取るのだから、少なくとも、1個は1を取らなければならない。 よって、求める和は少なくとも1以上である。 しかも、1は最大k-1個しかないので、求める和は最大でもk-1以下である。 証明終 定理1と定理2より、※は示された。」
その他の回答 (2)
- yoikagari
- ベストアンサー率50% (87/171)
訂正 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がわかる。」 の誤りです。
- yoikagari
- ベストアンサー率50% (87/171)
難しいかもしれませんが、証明を書いて置きます。 「n個の整数から、和がkで割り切れるk個の整数を取ることが出来る ⇔ n≧2*k-1・・・※ を示す。(k、nは自然数) 定理1 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が素数のとき、定理1は正しい。 証明 整数列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個の数字の和となる。 証明終 本題 定理1は正しい。 証明 数学的帰納法による。 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が合成数のときも定理1は正しい k=hのときも、定理1は正しいことが示された。 よって、帰納法により任意の自然数kに対して、定理1は正しい。 証明終 定理2 集合{0,・・・・,0(k-1個),1,・・・,1(k-1個)}からは、和がkで割り切れるk個の整数を選ぶことが出来ない。 証明 k個取るのだから、少なくとも、1個は1を取らなければならない。 よって、求める和は少なくとも1以上である。 しかも、1は最大k-1個しかないので、求める和は最大でもk-1以下である。 証明終 定理1と定理2より、※は示された。」
関連するQ&A
- 整数問題の証明
「ある整数n(n+2)が8の倍数ならばnは偶数であることを証明せよ。」 という問題で、この問題の解答を一応書いておくと、 「n(n+2)が8の倍数ならばnは奇数であると仮定すると、 n=2k-1(kは整数)とおいて、 n(n+2)=(2k-1)(2k+1)=4k^2-1より、 n(n+2)は奇数なので8の倍数になりえず矛盾。 ゆえにnは偶数である」 ですが、私は、 「n(n+2)が8の倍数ならばnは奇数であると仮定すると、 n(n+2)=8k(kは整数)と表せるので、 n^2=2(4k-n)となり、n^2は偶数だから、 nが奇数ならばn^2も奇数なので矛盾。 ゆえにnは偶数である」 と解いたのですが、これは解答として成立しますか? 違うのであれば具体的にどこが違うのかもお願いします。
- ベストアンサー
- 数学・算数
- 連続する3つの整数についての説明
文字式の利用という所なんですが、 問題は、2,4,6のように、一つおきに並んでいる整数の和は、3の倍数であることを説明しなさい。 nを整数とすると、一つおきに並んでいる3つの整数はn,n+2,n+4と表せる 従ってこれらの和はn+(n+2)+(n+4)=3n+6=3(n+2)となるなんですが、なぜ n+(n+2)+とんで(n+4)なのか、解りません。 (n+2)の次には(n+3)が入ると思っているんですが、 そもそも3の倍数は、6,9じゃないのですか?4は入らないのではないですか? よろしくお願いします。
- ベストアンサー
- 数学・算数
- 整数問題?がわからないので教えてください
nが自然数であるとき、n(n^3-1)(n^3+1)は偶数で、かつ7の倍数であることを示せ。 という問題なのですが、 nを奇数とするとn=2k+1(kは自然数)とおけ、与式=4k(2k+1)(4k^2+6k+3)(4k^3+6k^2+3k+1) までやってみましたが、よくわからないので、解答をお願いします。
- ベストアンサー
- 数学・算数
- 整数問題の質問です。
3で割ると1余り、5で割ると3余る2桁の最大の数を求めよ。という問題で、解説は、 3で割ると1余り、5で割ると3余る数の1つをaとおくと、a=3m+1 a=5n+2(m,nは整数)と表せる。3m+1=5n+3より、3m=5n+2 n=0,1,-1のうち、5n+2が3の倍数になるのはn=-1で、このときm=-1よってa=-2 求める数は15k-2(kは整数)と表せるので k=6のとき88となる。 となっているのですが、わからないことが2つあります。1つ目は、どうして n=0,1,-1にしたのかということで、2つ目は、a=2だとどうして求める数が15k-2(kは整数)になるのかということです。教えて下さい。
- ベストアンサー
- 数学・算数
お礼
確かに難しいですね。理解するのにかなり時間が掛かってしまいました。でも凄く丁寧な回答で分かり易かったです。 私もこういう問題が解けるように日々精進したいと思います。ありがとうございました。