nCmが奇数であることの必要十分条件は、２進記数表記で…

質問

自然数n,mを２進記数表記します。

n=2^p(1)+2^p(2)+ …、
m=2^q(1)+2^q(2)+ …

このとき、
{p(1),p(2), ...}⊃{q(1),q(2), ...} であることが、
nCm が奇数であることの必要十分条件である。

このことはどうやって証明できるのでしょうか？

回答No.2

totoro7683 · ベストアンサー

n=2^p(1)+2^p(2)+....+2^p(i)
m=2^q(1)+2^q(2)+.....+2^q(j)
とおきます。p(1)>p(2)>.....>p(i)>=0
q(1)>q(2)>.....>q(j)>=0とします。
nCm=n!/m!(n-m)!が奇数になるということは
n!とm!(n-m)!を素因数分解したときの２のべきが等しいということです。n!の素因数分解をn!=2^P*....とおく。
n!には2^(p(1)-1)+2^(p(2)-1)+....個の２の倍数があり、2^(p(1)-２)+2^(p(2)-２)+....個の４の倍数があり......１個の2^p(1)のばいすうがあります。これから
P=2^(p(1)-1)+2^(p(2)-1)+....＋2^(p(1)-２)+2^(p(2)-２)+....＋１＝2^p(1)-1+2^p(2)-1+....+2^p(i)-1=
n-iとなります。n!＝2^(n-i)*...
同様にm!の２のべき指数はm-jです。m!=2^(m-j)*...
ここでn-m=2^r(1)+2^r(2)+.....+2^r(k)とおきます。
(n-m)!のべき指数はn-m-kです。
nCm=n!/m!(n-m)!の分子の２のべき指数はn-i,分母はm-j+n-m-k=n-(j+k)
分母分子のべき指数はi=j+kのとき等しくなる。
{p(1),p(2), ...}⊃{q(1),q(2), ...} のときは明らかに
k=i-jである。もし{p(1),p(2), ...}⊃{q(1),q(2), ...} とならないときはi<j+kとなってしまう。
このような方針で証明してはどうでしょう。

お礼

うーんと納得、予想以上のご回答に感謝です。

>もし{p(1),p(2), ...}⊃{q(1),q(2), ...} とならないときはi<j+kとなってしまう。

これは２進数表記(0と1を使った表記)の筆算での加法を思い浮かべると、

　 m =2^q(1)+2^q(2)+.....+2^q(j)
+) n-m=2^r(1)+2^r(2)+.....+2^r(k)
------------------------------------
　 n=2^p(1)+2^p(2)+.....+2^p(i)

で繰上りが無いときが、j+k=iで、
「1+1=10」といった繰り上がりが１つでもあると、「1」の個数は少なくなり、j+k>iなのですね。

回答No.1

adinat

なかなかハイセンスな整数問題ですが、二項係数絡みなので、困ったときはパスカルの三角形を書いてみると何かひらめくことがあるかも知れません。パスカルの三角形を書いて、奇数になるものに○をつけてやると証明の方針が見えるかも．．．

具体的にどうするかといわれると、自然に思いつく方法としては数学的帰納法のように思います。命題P(n)を、

P(n)：1≦m≦nに対して、{p(1),p(2), ...}⊃{q(1),q(2), ...}ならばnCmは奇数

命題Q(n)を

Q(n)：1≦m≦nに対して、nCmが奇数ならば{p(1),p(2), ...}⊃{q(1),q(2), ...}

とおいて、それぞれnについての数学的帰納法で証明するわけです。その際、パスカルの三角形でも使用する性質、nCm+nC(m+1)=(n+1)Cmが役に立つと思います。

他にもよいアイデアがあるかも知れませんが、すぐには思いつきませんでした。

お礼

ありがとうございます。たいへん参考になりました。