FC2ブログ

Welcome to my blog

[答901] 組合せと偶数の個数

ヤドカリ

ヤドカリ



[答901] 組合せと偶数の個数


 0以上の整数nに対して、n0n1n2,……,nn のうち偶数であるものの個数を E(n) とします。

 (1) E(0)+E(1)+E(2)+……+E(50)=?

 (2) E(n)=901 のとき n=?


[解答]

 n0n1n2,……,nn のうち奇数であるものの個数を F(n) とし、

 F(m) から F(n) までの和を簡単に ΣF(m,n) と書くことにします。

 図はパスカルの三角形において、

 奇数を●,偶数を○で表し、右に n の値を2進法で書いたものです。

 nrn-1r-1n-1r だから、奇数●になるのは、両端および斜め上の2数が●と○のときだけです。

 以下、奇数●の配置について考察します。

 n=3=11(2) の場合、全部が●で 4個並んでいますが、

 n=4=100(2) の場合、両端だけが●になるので、

 n=4=100(2) ~ n=7=111(2) については n=0=0(2) ~ n=3=11(2) の配置を横に2個並べたものになり、

 n=7=111(2) には、全部が●で 8個並びます。

 n=8=1000(2) の場合、両端だけが●になるので、

 n=8=1000(2) ~ n=15=1111(2) については n=0=0(2) ~ n=7=111(2) の配置を横に2個並べたものになり、

 n=15=1111(2) には、全部が●で 16個並びます。

 このように、自然数kについて、

 n=2k-1 のとき、全部が●で 2k個並び、F(2k-1)=2k

 その下の n=2k のとき、両端だけが●で、F(2k)=2 です。

 また、例えば n=6=110(2) や n=10=1010(2) の行は

 n=2=10(2) の行を2個並べたものだから、F(6)=F(10)=2・F(2) です。 

 一般に、2進法で n を表したとき、上位に 1 がひとつ増えれば、F(n) は2倍になります。

 従って、F(0)=1=20 を元にすれば、F(n)=2k ( k は n を2進法で表したときの 1 の個数) となります。

 (1) n=0 ~ n=15 は2進法で4桁以下で、1 が k 個の数は 4k 個だから、

  ΣF(0,15)=2040+2141+2242+2343+2444=(1+2)4=81 、

  16=10000(2) より ΣF(16,31)=2・ΣF(0,15) 、32=100000(2) より ΣF(32,47)=2・ΣF(0,15) 、

  ΣF(0,2)=1+2+2=5 、48=110000(2) より ΣF(48,50)=22・ΣF(0,2) 、

  ΣF(0,50)=(1+2+2)・ΣF(0,15)+4・ΣF(0,2)=5・81+4・5=425 、奇数は 425個です。

  奇数偶数を合わせて 1+2+3+……+51=51・52/2=1326 個だから、偶数は 1326-425=901 個です。

 (2) E(n)+F(n)=n+1 だから n=E(n)+F(n)-1 、E(n)=901 のとき n=900+F(n) です。

  900+2k=1110000100(2)+10(2)k より

  右辺を2進法で計算して 1 の個数が k 個になるのは k=5 のときだけだから、

  n=900+25=932 です。

.

スポンサーサイト



Comments 17

There are no comments yet.
ひとりしずか  
No title

テッポウユリでしょうか~
いっぺんにこんなにたくさんの咲くゆりは見たことないです

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
仰る通り、テッポウユリです。
白いユリが清々しく咲いていました。

樹☆  
No title

おはようございます

雨は上がりましたが・・梅雨空らしいどんよりです。
そんな中、美しいテッポウユリに心が
洗われるようです。

ニリンソウ  
No title

清楚な白百合を美しく撮りましたね!
たくさん咲いていたんでしょう
香が届きました。

ナイス

tsuyoshik1942  
No title

この○と●からなるパスカルの三角形には思い至りましたが、それを解答にまとめ仕上げることは出来ませんでした。
答の算出にはPCの力を借りてしまいました。

なお、E(n),F(n)とも数列大事典「A048967,A001316]に登録されておりました。

uch*n*an  
No title

この問題は,規則性は比較的容易に分かり解けたのですが,それをどう表現し使うかで苦労しました。
幾つかの解法の後にやっと2進数表記が有効なことに気付き,スッキリと解けました。

たけちゃん  
No title

私は,二項係数nCkそのものというより,nCk=(n!)/(k!(n-k)!)に着目し,
m!が2で何回割り切れるかを考えました.
その回数は,[m/2]+[m/4]+[m/8]+…であり,
mを2進法で表して末尾から順次1桁ずつ削ったものの和です.
例えばm=101001(2)であれば,回数は,
10100(2)+1010(2)+101(2)+10(2)+1(2)であり,
(100000(2)-1)+(1000(2)-1)+(1(2)-1),つまり,101001(2)-3となります.
このように,m!が2で割り切れる回数は,m-(mの2進表示での1の個数)となるので,
nCkが奇数となる条件は,k+(n-k)を2進法で計算したとき繰り上がりが生じないこと,
すなわち,n,kを2進法で表すとき,nで0となっている桁ではkも0となることであり,
nで1となっている桁について,kは0でも1でもよいので,
奇数の個数(解答でのF(n))は,2^(nの2進表示の1の個数)とわかります.

たけちゃん  
No title

今年の東京大学の入試問題で,
「2015Cmが偶数となる最小の自然数mを求めよ.」
というのが出題されていますが,本問は,それより難しいのは確かだと思います.

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!をありがとうございます。
晴れると日差しが強く、雨になるとかなりの量、
過ごしにくい日々が続きますが、白百合で爽やかな気持ちになってくれれば幸いです。

ヤドカリ  
No title

ニリンソウさん、早速のコメントとナイス!をありがとうございます。
たくさんのユリが咲く季節になりました。
野山に咲く1輪の百合もいいですが、固まって咲くのもいいですね。

ヤドカリ  
No title

tsuyoshik1942さん、早速のコメントをありがとうございます。
パスカルの三角形で偶数と奇数に分けると形が見えてきますね。
それを表現するのに苦労する問題です。
数列大事典にこんなことまで載っているのですね。

ヤドカリ  
No title

uch*n*anさん、コメントをありがとうございます。
偶数奇数ですので2進法と関係があることは分かりますが、
大抵の問題は2進法を使わなくても大したことはありません。
そんな中で2進法でスッキリするものを見つけました。

ヤドカリ  
No title

たけちゃんさん、コメントをありがとうございます。
貴殿の解き方を拝見し、
偶数より奇数の個数の方がスッキリした式になるのに
何故偶数の個数を直接求めておられるのか、
不勉強な私には分からなかったのですが、
背景に今年の東大の問題があったのですね。
この問題で納得できました。

さっちゃんこ  
No title

こんばんは
真っ白のユリは清純な乙女のようでいいですネ
質素な感じが大好きです
ナイス☆彡

ヤドカリ  
No title

さっちゃんこさん、コメントをありがとうございます。
白いユリには清純なイメージがありますね。
かなりの量の花粉が写ったのは残念でした。

スモークマン  
No title

グーテンアーベント ^^
みなさんさすがですねぇ☆
わたしゃ…この問題も全然気づけず…^^;
面白い問題を次々と思い付かれるものだと指をくわえてただ感心頻り☆
11を一つ右にずらして101
101をずらして1111
1111をずらして10001
のように考えてはみたものの...規則が見つけられずもどかしい日々を悶々と…^^;;
熟読玩味ぃ~です…Orz~

ヤドカリ  
No title

スモークマンさん、コメントをありがとうございます。
2進法を考えられたのですね。
それとの関連に気づけばよかった問題でした。