連続するn個の数

質問

連続するn個の数の積がn!で割り切れるのはなぜですか。
nCrは組み合わせを意味する、などといった計算の意味ではなく
すっきりと説明できるのでしょうか。

回答No.4

funoe · ベストアンサー

mに関する数学的帰納法を使う。

肝は、mCn = (m-1)C(n-1) + (m-1)C(n)
が恒等式であることを用いる。
（代数的に示すべきですが、パスカルの三角形から明らかです）

補足

確かに帰納法を使えば示せますね。
ただ、できればもっと直感的に、式変形で示せればよいのですが…

回答No.10

YHU00444

ANo.9一番目の※に関しては

>これが4!で割れないのは、「連続するnコの整数の中には(n+1)の倍数を陽に含まない組み合わせが存在し得る」というだけの話で、n!で割れるかどうかとは無関係。
と訂正します。（どうも失礼しました）

お礼

了解しました。何度も解答していただきありがとうございました。

回答No.9

YHU00444

では1の補足の例を参考に考えてみましょうか。

(3*4*5)は連続する3コの自然数の積であり、3については3*1、2については4=2*2、と3および2を約数に含む数をもちますが、この連続する部分列3,4、もしくは4,5には2を約数として持つ数が必ず含まれます。
※ちなみにこれが4で割れないのは、「連続するnコの整数の中には(n+1)の倍数を含まない組み合わせが存在する場合もある」というだけの話で、n!で割れるかどうかとは何の関係もありません。

また、151*152*153*154*155*156*157*158*159の組み合わせを考えると、たとえば、8コの連続する部分列151～158もしくは152～159は8の倍数を必ず含んでいますし、6コの連続する部分列151～156、152～157、153～158、154～159は必ず6の倍数を含みます。しかし10の倍数についてはそうではない。

こうなるのはkの倍数の間隔を考えれば明らかです。
そもそもkの倍数は、kの倍数でない数を(k-1)コはさんで並んでいますから、ここから連続するkコの整数をとった場合、k（そのもの）を約数に含む数は「少なくとも必ず1コは」存在します。なぜなら連続してkの倍数を含まない数は(k-1)コしかないので、それをどう組み合わせたってkコの並びは作れないから。

よってnコの連続自然数に対して適当に連続する部分列をとれば、それは必ず部分列の個数に対応する約数を「少なくとも必ず1コ」含むし、k≦nであれば必ず連続するkコの部分列を取れるのも自明ですから、Aは任意のk(k≦n)を約数として「少なくとも必ず1コは」含むことが分かるわけです。

回答No.8

atomicmolecule

no.4さんの帰納法の証明をちゃんと考えてみてください。その中にn個の何故連続する整数の積がn!で割り切れるかが見えてきます。

お礼

No.4さんの証明は以下のようになりました。

mCn(1≦n≦m)が全て整数となることを証明する。
・m=1のとき
1C1=1により成り立つ。
・m=kでの成立を仮定するとkC1,…,kC(n-1),kCn,…kC(K-1),kCkは全て整数である。m=k+1では
(k+1)Cn=kC(n-1)+kCn
右辺はm=kでの仮定により整数ゆえm=k+1でも成り立つ。

少しずつ何故割り切れるのか、直感的に感じられるようになってきました。
ありがとうございます。

回答No.7

thetas

以下のような手法ではいかがですか。
（ただし、答案として不備があることを初めに書いておきます。）

n!を素因数分解し、各素数について注目します。
例）４！＝２＾３×３
　このとき、「４！で割り切れること」と、
「８（＝２＾３）で割り切れ、３で割り切れること」は同値であることを確認しておきます。

まず、素数２について考えますと、
１～ｎの中に
２の倍数は［ｎ／２］個　　（注．［］はガウス記号）
２＾２の倍数は［ｎ／４］個
・・・
２＾ｋの倍数は１個　　（注．ｋは、２＾ｋ≦ｎ＜２＾（ｋ＋１）を満たす自然数）
とかけます。
よって、n!を素因数分解すると、２の次数は［ｎ／２］＋［ｎ／４］＋・・・＋１となります。

一方、ｎ個の連続する自然数の中には、
２の倍数は、少なくとも［ｎ／２］個あります。
記号を見やすくするために、ｊ＝［ｎ／２］と書きます。
次に、４の倍数の個数ですが、
ｎ個の連続する自然数の中には、少なくともｊ個の偶数があります。
そのｊ個の偶数（ｊ個を超えるときは、小さい順に取り出したｊ個だけを考えることにします）
は、ｊ個の連続する自然数に２をかけたものです。
そして、ｊ個の連続する自然数の中には、［ｊ／２］個の偶数があります。
ということは、ｎ個の連続する自然数の中にある４の倍数は、［ｊ／２］個あります。
つまり、［ｊ／２］＝［［ｎ／２］／２］＝［ｎ／４］となります。

これを繰り返せば、
ｎ個の連続する自然数の中には、
２の倍数は少なくとも［ｎ／２］個
２＾２の倍数は少なくとも［ｎ／４］個
・・・
２＾ｋの倍数は少なくとも１個
あることが分かります。

これにより、
（ｎ個の連続する自然数の積を素因数分解したときの２の次数）≧（n!を素因数分解したときの２の次数）

これを、ｎ以下の素数で確認をすればいえそうな気がします。
ただ、これを書き終えてみると、すっきりとはいえませんね。
蛇足ながら、私自身としては、もう少し大雑把に上記のことを考えていたので、もっと簡潔に書けるものと思っていました。

お礼

除数を素数に分けてそれぞれの素数について考えていくわけですね。
反論の余地はありません、ブラボーだと思います。
ありがとうございます。

回答No.6

YHU00444

ANo.3ですが、
>n以下の全ての自然数でそれぞれ割り切れてもn!で割り切れるとは限らないのではないですか？
にはビックリしました（笑）。（ネタじゃないですよね？）

ならばしつこいくらいに説明しましょうか。
◆の考察から、連続するnコの整数の中には「nそのもの」を約数に含む数が必ず存在することが解ります。また、部分列として「kそのもの（k<n）」を約数に含む数も必ず存在するわけです。（←大事なのはこの部分）
ですから、その積のAはk(k<n)をすべて（余すところなく）約数として含みます。

これを式で表現すればA=n(n-1)(n-2)…2*1*Bとなるのは明らかでしょう。

補足

ネタじゃないです。いたって真面目です。

申し訳ないのですが
"部分列として「kそのもの（k<n）」を約数に含む数も必ず存在する"
の部分が良く分かりません。具体例で示していただけるといいのですが。

回答No.5

noname#101087

>(3*4*5)/(4*3*2)
>を考えると割るほうのそれぞれに合同な数があるのに割り切れないのではないですか？

ANo.1 さんのコメントには「行間」があります。(一行に収まってはいますが ...)

　n個連続しているので、その中に必ず、ｎと合同な数がある。
　(ここで、ｎとnの合同数を脇によけておく。残った数について....)
　同様に１からｎ－１までの数と合同な数がある。

ｎとnの合同数を脇によけても大丈夫なのは何故か、考えてみてください。

補足

「ｎとnの合同数を脇によけておく」
というのは
たとえば
6*5*4/3*2*1ならば3と6をよけて、2と4をよけてると5/1で割り切れるということですか？しかし
7*6*5/3/2/1ならば3と6をよけると7*5/2*1となり合同な数はなくなってしまうのですが…

回答No.3

YHU00444

要するに「連続するnコの整数の積がnで割り切れる（◆）」ことが言えるなら芋づる式に題意が示せますよね。だって、連続するnコの整数の中には、必ず連続するkコ(k<n)の整数が存在するんだから◆が言えればkで割り切れるのも同時に言えるはず。

で、◆については隣り合うnの倍数の間隔を考えてやれば証明は簡単でしょう。

補足

n以下の全ての自然数でそれぞれ割り切れてもn!で割り切れるとは限らないのではないですか？

回答No.2

noname#24129

連続するn個の自然数をa_1,a_2、・・・a_nとあらわしますね。連続するためには、n>1でなければなりませんね。n=2の場合から考えてみましょう。

n=2のとき、
(a_1)*(a_2)/2は、割り切れるとおもいませんか。というのは、(a_1)と(a_2)は連続しているので、どちらか一方は、偶数のはずだからです。

n=3のとき、
(a_1)*(a_2)*(a_3)/(3*2)
これも割り切れますね。なぜなら、連続している(a_1),(a_2),(a_3)のうち、いずれか1つは３の倍数であり、また、偶数も含んでいるはずだからです。

n=4からさきも、同じことがいえそうですね。あとはこれを、数学的にどう表現したらいいかということになりますかね。

補足

「n=4からさきも、同じことがいえる」というところが分かりません。
分母のa*b*c*…の部分が互いに素ならば対応する数が違うので割り切れますがそうでないので成立しないのではないですか。

回答No.1

N64

n個連続しているので、その中に必ず、ｎと合同な数がある。同様に１からｎ－１までの数と合同な数がある。ではだめでしょうか？

補足

回答ありがとうございます、がすっきりしません。
例えば（条件からは外れますが）
(3*4*5)/(4*3*2)
を考えると割るほうのそれぞれに合同な数があるのに割り切れないのではないですか？