０と１からできる数字の列の全体を次のように１列に並べる

質問

０と１からできる数字の列の全体を次のように１列に並べる

0,1.00,01,10,11,000,001,010,011,100,101,110,111,0000,.......

Xがｎ番目の項であるとき、Ｘの後に１を加えた項Ｘ１は何番目に現れるか。ｎ式で示せ。

この問題がわかりません。教えてください。「やさしい理系数学」の６６番の問題です。

回答No.5

naniwacchi · ベストアンサー

#3です。

単に、10を 2に変えるだけなんですが・・・

「10進法で Xが n番目の項であるとき、X1は何番目か？」
⇒ 「2進法で Xが n番目の項であるとき、X1は何番目か？」

・10倍するとケタが 1つ上がるので、X0は 10n番目であることがわかります。
⇒ 2倍するとケタが 1つ上がるので、X0は 2n番目であることがわかります。

・それに 1を加えると X1になるので・・・
そのままですね・・・

ただし、いまの問題は「0からスタートして（数え始めて）」います。
「X1」の数字の大きさとしては「2n+1」となりますが、
全体で何番目ということを考えると 2n+2番目ということになります。

回答No.4

Mr_Holland

ｎ番目の桁数をｋとします。
　（ここで　ｋの具体的な式は不要ですが　敢えて書けば　k=[log_2(n+1)]　になります。ただし、 [x]はガウスの記号でｘを超えない最大の整数を返します。）

　すると、桁数が増えるときのｎの値は次のようになります。
　　1+Σ[i=1→k-1] 2^i =2^k -1

　従って、Xを2進数で読んだときの値は次のようになります。
　　n-(2^k -1)

　さて、X1を2進数で読んだときの値は　Xを2進数を読んだときの値を2倍して１を加えたものになりますので　次のように表されます。
　　2{n-(2^k -1)}+1

　X1の桁数は (k+1)桁になりますので、(k+1)桁になる最初の項は　2^(k+1)-1 番目に現れます。
　従って、X1がn'番目に現れるとすれば、n'は次のように表されます。

　　n'=2{n-(2^k -1)}+1 + 2^(k+1)-1 =2(n+1)

お礼

難しい解答ですね＾＾；何度も読んでみます。ありがとうございました。

回答No.3

naniwacchi

こんにちわ。

高校数学の範囲で考えるのであれば、群数列の問題と見ることができます。

が、2進法がわかっていると、速攻で解けてしまいます。
少し違った例を考えてみましょう。
「10進法で Xが n番目の項であるとき、X1は何番目か？」
・10倍するとケタが 1つ上がるので、X0は 10n番目であることがわかります。
・それに 1を加えると X1になるので・・・

これと同じようなことを 2進法で考えます。
群数列で考えるよりも、この方がはるかに速く解けてしまいます。＾＾

お礼

２進法はある程度理解してるつもりなので２進法の解答が知りたいです＞＜

回答No.2

nattocurry

この数列は、次のように解釈することができます。

まず、0,1がある。
その後に、1番目の数字(0)の後に0を足したもの00と1を足したもの01を並べてある。
その後に、2番目の数字(1)の後に0を足したもの10と1を足したもの11を並べてある。
その後に、3番目の数字(00)の後に0を足したもの000と1を足したもの001を並べてある。
その後に、4番目の数字(01)の後に0を足したもの010と1を足したもの011を並べてある。
その後に、5番目の数字(10)の後に0を足したもの100と1を足したもの101を並べてある。
：
：
：
その後に、n番目の数字(X)の後に0を足したものX0と1を足したものX1を並べてある。

Ｘがｎ番目の項であるとき、Ｘの後に１を加えた項Ｘ１がｍ番目に現れるとすると、ｎが１増えるにつれて、ｍは２増えることが解ります。

そして、ｎが１のときに、ｍは４です。
Ｘ＝０が１番目で、Ｘ１＝０１が４番目なので。

ということは、ｍ＝２ｎ＋２と表すことができます。

よって、答えは２ｎ＋２

お礼

おもしろい解答ですね。その見方なわたしにはできませんでした。ありがとうございます。

回答No.1

nag0720

計算でできないこともないけど、実際に調べたほうが早いです。

0 (1番目) → 01 (4番目)
1 (2番目) → 11 (6番目)
00 (3番目) → 001 (8番目)
01 (4番目) → 011 (10番目)
10 (5番目) → 101 (12番目)
11 (6番目) → 111 (14番目)
000 (7番目) → 0001 (16番目)
001 (8番目) → 0011 (18番目)
010 (9番目) → 0101 (20番目)
011 (10番目) → 0111 (22番目)

n番目は何番目になってますか？

お礼

回答ありがとうございます。数学的帰納法で証明できそうですね。計算の方も知りたいです。