問題13015・・・
http://blog.livedoor.jp/uyama_yuichi/archives/66065030.html より 引用 Orz〜
ある整数に対して、次のような操作(ア)または(イ)を、
その結果が1になるまでくり返し行います。
(ア)偶数は2で割ります。
(イ)奇数には1を加えます。
16回の操作で終了する整数は、全部でいくつありますか?
(1993年.筑波大附属駒場中3番(4)改題)
解答
・わたしの…
3回なら…
1-2-(4,3)-((8,7),(6,5))-・・・1+1+2+2^2=2^3
so…
16回なら…
1+1+2+2^2+…+2^15=2^16=65536個
ね ^^
↑
誤ってました ^^; Orz…
↓
・鍵コメT様からのもの Orz〜
1←2ですが,2←(3,4)は誤りで,3からは2ではなく4に移行します.
以下,2←4,3←6,4←(3,8),5←10,6←(7,12)のようになります.
つまり,1回の操作でnになる数(「nの親」ということにします)は,
nが正の奇数または2のときは2nだけであり,
nが4以上の偶数のときはn-1,2nの2つとなります.
「奇数または2」をA型,それ以外の自然数をB型としましょう.
1以外のA型の数nの親2nはB型であり,
B型の数nの親は,n-1がA型,2nはB型です.
自然数kに対して,k回の操作で終了するような自然数のうち
A型の個数をa[k],B型の個数をb[k]とすると,
a[1]=1,b[1]=0 (1回で終わるのは「2」のみ)であり,
A型の数a[k]個はそれぞれ1つのB型の親をもち,
B型の数b[k]個はそれぞれA型,B型の親を1つずつもつので,
a[k+1]=b[k],b[k+1]=a[k]+b[k]となりますね.
求めるものa[16]+b[16]はb[17]であり,
b[2]=1,b[k+2]=b[k+1]+a[k+1]=b[k+1]+b[k]となって,
{b[k]}:0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,…
となるので,求める個数は987です.
*漸化式で考えればいいことはわかりました ^^☆
but...小学生には酷な気もしたり…^^;...