コンビネーションの問題

質問

コンビネーションの問題で、n_C_k　で、ｋを１～n-1まで動かしたときに、すべて３で割切れるためのnの条件を求める問題で、どのように考えたらいいのか困っています。
n=1で成り立つことが必要だからnは3の倍数、くらいは分かるのですが、このあとどのように考えたらいいのでしょうか。ご教授お願いします。

回答No.3

ramayana · ベストアンサー

ANo.1 の [2] が必要条件であることの、もっと簡単な証明を思いつきました。

************

n = q3^r （qは3で割り切れない）とする。すると、mod 3 で、

(X+1)^n ≡ ((X+1)^(3^r))^q ≡ (X^(3^r)+1)^q
　　　　　≡ X^(3^r) + qX^(3^r-1) + …

となって、これは、X^n + 1 と合同でない。

************

一般に、 p を素数とするとき、

(X+1)^p ≡ X^p +1 mod p

なので、上の論法は、3を p に置き換えても有効です。よって、次が言えます。

[3]　　p が素数のとき、(X+1)^n ≡ X^n + 1 mod p となるのは、適当な正整数 r によって n = p^r となるときで、かつ、そのときに限る。

さらに、次のことも分かります。

[4]　　m が素数以外の正整数のとき、(X+1)^n ≡ X^n + 1 mod mとなる正整数 n は、存在しない。

お礼

丁寧な書き込みありがとうございます。

適当な正整数ｒとありますが、ようは３の累乗の数列{３，９，２７，８１，・・・}でよろしいわけですね。

回答No.4

nag0720

失礼、＃２は全然違ってましたね。

回答No.2

nag0720

n_C_k=n!/k!(n-k)!
なので、n!の素因数の中に3がいくつ入っているかを調べる必要があります。
それをS(n)で表すことにします。
つまり、S(1)=0、S(3)=1、S(6)=2、S(9)=4、・・・

そうすれば、問題は、
1≦k≦n-1であるすべてのkについて、S(n)＞S(k)+S(n-k)
となるnを求めることと同じです。

S(n)=[n/3]+[n/3^2]+[n/3^3]+・・・・
だから、これをもとにnを調べてみてはいかがですか。

予想としては、
nは2*3^pではない3の倍数

n=2*3^pの場合は、
S(n)=S(2*3^p)=2*3^(p-1)+2*3^(p-2)+2*3^(p-3)+・・・+2*3+2*1=3^p-1
S(n/2)=S(3^p)=(3^p-1)/2
なので、k=n/2のときS(n)=S(k)+S(n-k)なので条件を満たしません。

それ以外の3の倍数のときは条件を満たすような気がします。

回答No.1

ramayana

ご質問は、

[1]　　(X+1)^n ≡ X^n + 1 mod 3

を満たす n を求めよ、ということですね。

[2]　　 適当な正整数 r により n = 3^r

として、[2]が[1]の十分条件であることは、すぐ分かります。必要条件であることは、次のようにして示すことができます。

************************

[1]を満たす n があったとして、その次に[1]を満たすn を n' とする。n' = n + m と置く。

(X+1)^n' = (X+1)^n・(X+1)^m ≡ X^(n+m) + 1 mod 3

である。(X+1)^m = Σ[k=0,m]a[k]X^k と置けば、

[3]　　(X+1)^n・(X+1)^m
　　　　　　　≡Σ[k=0,n-1]a[k]X^k
　　　　　　　　　+Σ[k=n,m](a[k-n] + a[k])X^k
　　　　　　　　　+Σ[k=m+1,m+n] a[k-n] X^k mod 3

上の式で、X^0 と X^(m+n) 以外の係数がすべて 0 mod 3 となることから、

　　a[0] ≡ 1、a[n] ≡ 1、a[2n] ≡ 1
　　a[k] ≡ 0 （上記以外の k ）

を得る（細部は省略）。これらから、m = 2n すなわち、n' = 3n を得る。