• ベストアンサー
  • 暇なときにでも

整数の問題

この前友人が私に出した問題です。 自然数kに対して、次の条件を満たす自然数nの最小値を求めよ。 「任意のn個の整数において、その中から上手くk個を選べば和をkの倍数にすることができる。」 例)k=2のとき…n=2ならば偶奇が異なるとき条件を満たさず、n=3ならば偶奇が一致する二整数が必ず存在するのでnの最小値は3。 k=5まではn=2k-1という関係になったそうです。kが6以上のときもそうなるのか(その場合は証明可能かどうか)、或いは全く関係の無い値になるのか知りたいのだが何か良いアイデアは無いかと聞かれました。 取り敢えずk=6について調べてみようとしましたが分岐が多いので断念しました(k=5でも結構大変そうですが…)。 良い方法がありましたら教えて下さい。

noname#20999
noname#20999

共感・応援の気持ちを伝えよう!

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.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)

  • 回答No.2

訂正 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

難しいかもしれませんが、証明を書いて置きます。 「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^3+5nが3の倍数であることを示せ」 という問題があれば、n=3k、n=3k±1とおいて式に代入しますよね。 整数問題を扱った参考書を見ると、k:整数として置いているのですが、 n^3+5nに実際にn=3kを代入し、 n^3+5n=3(kの式)となっても、kは整数という条件なのでこれにk=0を当てはめれば0になってしまいます。 質問(1) 上の説明 質問(2) k:自然数 とおいて議論を進めても減点はされないのか よろしくお願いします。 もしかすると0も3の倍数…?

  • センターの整数問題

    こんばんは。センターの模試で質問があります。こんな問題です。 M、Nは自然数として、 「Mが2の倍数でかつ3M+2Nが6の倍数でない」ならば「N^2+αは3の倍数」が真であるような2桁の自然数αは□□個ある。 解答は、2Nが6の倍数でないからNは3の倍数でないということに注目してN=3L+-1(L整数)だからN^2+α=3(3L^2+-2L)+1+α として求めてます。確かにこれで解けますが、なぜ突然Nの倍数性に注目しようとしたのでしょうか? すみませんが教えてください!

  • 整数問題の証明

    「ある整数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を加えた数Nは12の倍数であるが,24の倍数ではないことを証明せよ という問題で (証明)連続する3つの奇数は2k±1,2k+3とおける(kは整数) (2k±1)^2+(2k+3)^2+1 =4k^2±4k+1+4k^2+12k+9+1 =8k^2±4k+12k+11で答えと一致しません どこが間違っているのでしょうか? ±を使ってはいけないのかもしれないのですが、それなら何故使ってはいけないのかそれも教えて下さい どうぞお手数をお掛けしますがよろしくお願いします。

  • 整数の問題

    次の問題が解けなくて困っています。 nは自然数である。 (1)nが4の倍数のとき、n=x^2-y^2を満たす整数x,y(x>y≧0)があることを示せ。 (2)nが奇数のとき、n=x^2-y^2を満たす整数x,y(x>y≧0)があることを示せ。 どうか分かりやすい解説よろしくお願いします。

  • 整数の問題(高1)

    次の問題がわかりません。ご教授ください。明日提出なので、かなりせっぱつまっています汗 (1)各位の数の和が9の倍数であるような整数は、9の倍数である。このことを、4桁の整数の場合について証明せよ。 (2)nは整数とする。n(5n^2+6n+1)は6の倍数であることを証明せよ。 (3)連続した3つの奇数の平方の和に1を加えた数は、12の倍数であるが、24の倍数でないことを証明せよ。

  • 整数問題の質問です。

    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は整数)になるのかということです。教えて下さい。

  • 整数問題

    連続する3つの整数の積は6の倍数であることを示せ。 という問題なんですが、 任意の整数を n とおいて n(n+1)(n+2)と とりあえず置きました。 これを展開したりしてみましたが6の倍数であることを示せそうな式になりませんでした。 こんなときは (1) 1×2×3=6 (2) 2×3×4=24  (3) 3×4×5=60 (4) 4×5×6=120 (5) 5×6×7=210 ゆえにどれも6の倍数であるから 連続する3つの整数の積は6の倍数である。 と答えた場合 試験官はいくらか点数をくれるでしょうか? それとも 式で表さなければいけないのか。 証明の仕方も教えていただけたら助かります。