19739：負でない整数N,a(1)=M.a'n+1)=[a(n)/2],[ ]はガウス記号,0<=N<2^10でNから始まる数列a(n)のある項が2となるものはいくつ？

この花の名は...「アベリア」でしたよね ^^

アベマリアで覚えてました ^^;v

問題19739・・・http://officeklu.s502.xrea.com/2014mondai/ より 引用 Orz〜

解答

・わたしの...

(1)

a(3)=[a(2)/2]=1

a(2)=2,3

a(2)=[a(1)/2]=2・・・N=a(1)=4,5

a(2)=[a(1)/2]=3・・・N=a(1)=6,7

so...N=4,5,6,7

(2)

2-(4,5)-((8,9),(10,11))-(((16,17),(18,19)),((20,21),(22,23)))-...

1+2+2^2+...+2^(9-1)=2^9-1=512-1=511個

(3)

どのNにおいてもという意味だから...Nが最大の時で考える...

2が現れる個数は2^99-1

(2^99-1)/2^100<1/2

so...

2^7=128

so...2^93

so...2^7 なら...

2^7〜2^99・・・2^7から1+2+2^2+...+2^92=2^93-1

この時...

(2^93-1)/2^100<1/2^7

so...m=2^7=128

かいなぁ...^^;

・鍵コメT様からのもの Orz〜

(3)は，正しい結論だと思いますが，根拠は少々怪しいです．
そもそも題意は， 「どのNについてもという意味」ではありません．
Nは初項であり，0〜2^100-1までのどれかを等確率(1/2^100)で初項を選び，
値がmである項が登場する確率を1/100以下にする問題です．

数列{a[n]}の各項を2進法で表すと，各項を定める規則は，
「直前の項が2(=10[2])以上であれば，その末尾の数字をカットする．
直前の項が0,1であれば，新たな項は0とする．」
のようにすっきり表されます．
mを自然数として，この数列に値がmである項が登場するのは，
mを2進法で表したときの桁数をkとして，
「Nが2進法でk桁以上であり，かつ，Nの2進法表示で末尾から
0個以上の数字を除いてk桁としたときにmの2進法表示と同じになる」
場合です．

Nの範囲0≦N≦2^100-1のうち，Nが2進法表示でk桁未満の場合(2^(k-1)個)
は明らかに条件を満たさず，
k桁以上の場合は，{a[n]}の項のうちに2進法でk桁となるものが1つだけあり，
その項が，2進法でk桁の自然数2^(k-1)個のどれであることも等確率なので，
ある項がmとなるNは，(2^100-2^(k-1))/2^(k-1)通りあり，
題意の確率は，これを2^100で割って，1/2^(k-1)-1/2^100となります．
1/100以下となるのはk≧8の場合であり，求める最小のmは，
1000000[2]=128です．

してみると，(2)を同様に考えることもできるのがわかります．

0≦N<2^10を満たす2^10個のNのうちで，ある項が2=10[2]となるのは，
Nが2進法で2桁以上であり，a[n]のうちの2進法で2桁の項が
10[2]=2,11[2]=3のうちの2である場合であって，
その個数は，(2^10-2)/2=511(個)となります．

*2進法で考えるのが本質的な解法と思いますが...beyond me...^^; Orz〜

*最大のmではないかと血迷った疑問を持ってましたが...^^;;

↓

・鍵コメT様からの解説頂戴 Orz〜

「数列{a[n]}のある項がmとなる確率」は，紹介いただいたコメントから，
m=2,3に対して1/2-1/2^100,m=4,5,6,7に対して1/2^2-1/2^100,
m=8〜15に対して1/2^3-1/2^100,…,m=128〜255に対して1/2^7-1/2^100,
m=256〜511に対して1/2^8-1/2^100のようになります．

確率が1/100以下となるmは，128以上の自然数すべてであり，
題意は当然「最小のm」です．

*そうでしたわ ^^;v

[スモークマン]

＞10:27pmの鍵コメT様へ ^^
あるNを選んでa(k)=mが出る確率が1/100以下なので...
あるN以下では確率0<1/100なので、Nが最大の時でも1/100以下になる場合をアバウトに考えてみました...(2)からのアナロジーで、あるm以上が2^93個あれば、...m,2*m,2^2*m,...,2^92*m=2^99・・・1+2+2^2+...+2^92=2^93-1<2^93
(2^93-1)/2^100<2^93/2^100=1/128<1/100
みたいなことを考えました...^^;

紹介させていただきまっす〜m(_ _)m〜v

[スモークマン]

＞11:15pmの鍵コメT様へ ^^
でした...^^;
あるN以下では確率0なので...Nが最大のとき1/100以下になる最大のmを選べば、Nが何であれ満たすと考えました...
問題文は最小のmを求めるとなってますが、最大のmですよね？...^^

[スモークマン]

＞11:31pmの鍵コメT様へ ^^
そうか、そうか...^^;
範囲が最大と...ごちゃごちゃになってましたわ Orz〜
紹介させていただきまっす〜m(_ _)m〜v