中学入試の問題です。教えてください。

質問

ある数について、その数が奇数の場合は１とし、偶数の場合は２で割るという作業をくり返し行い、その結果が１になるまで続けます。例えばある数が６の場合、６→３→４→２→１のように、４回の作業で終わります。
(1)　ある数が18のとき、何回の作業で終わりますか。
　　　　これはわかりました。８回です。
(2)　３回の作業で９となる数を全部書きなさい。
　　　　これは、おそらく、34、35、72かと思います。
(3)　９回の作業で終わる数は全部でいくつありますか。
　　　　これがどうしてもわからないのです。解き方を教えてください。お願いします。

回答No.3

siyono314 · ベストアンサー

答えは34です。

まず、最後が1になるためには、最後の1つ前（最後から2番目）が2でなくてはなりません。（1を足して1になるのは0であるが、1を足す、または2で割るという作業の中で0がでてくることはないため。）

そして、最後から3番目は、1を足して2になる数、または2で割って2になる数ですが、1を足して2になる数は1であり、この場合はここで作業が終了してしまうので、2で割って2になる数、つまり4になります。

次に、最後から4番目は、1を足して4になる数、または2で割って4になる数なので、3または8になります。

最後から5番目は、最後から4番目が3の場合は、1を足して3になる数、または2で割って3になる数だから、2または6ですが、2は偶数であり、奇数の場合は1を足し、偶数の場合は2で割るという条件に当てはまらないので、6だけになります。
また、最後から4番目が8の場合は、1を足して8になる数、または2で割って8になる数なので、7または16です。

最後から6番目は、最後から5番目が6の場合は、1を足して6になる数、または2で割って6になる数なので、5または12になります。
また、最後から5番目が7の場合は、1を足して7になる数、または2で割って7になる数なので、6または14ですが、6は偶数であり、奇数の場合は1を足し、偶数の場合は2で割るという条件に当てはまらないので、14だけになります。
また、最後から5番目が16の場合は、1を足して16になる数、または2で割って16になる数なので、15または32になります。

このように、順番にさかのぼっていくと、最後から10番目の数、つまり作業を9回行うとで1になる数が34個出てきます。

ただし、途中で奇数が出てきた場合、1を足して奇数になる数は偶数であるため、奇数の場合は1を足し、偶数の場合は2で割るという条件に当てはまらなくなることに注意してください。

ゆっくり落ち着いて解いていけば、きっと解けると思いますよ。

お礼

大変丁寧に説明していただきありがとうございます。

回答No.4

jamf0421

（３）についてですが、規則を逆にたどるとどうなるかをお考えになってはいかがでしょうか？
4から先で枝分かれです。規則は
偶数→2倍、1マイナス
奇数→2倍
逆にいえば、遡るにあたり偶数は偶数と奇数から来て、奇数は偶数からきます。
です。この規則を纏めるのに、n段目の偶数の個数をEn、奇数をの個数をOnとすれば
En=En-1+On-1....(1)
On=En-1...(2)
(1)を(2)を考慮して書き直すと
En=En-1+En-2..(1)'
(2)を(1)と(2)自身を考慮して書き直すと
On=En-2+On-2=E-2+En-3...(2)'
となります。偶数と奇数ともフィボナッチ数列で数が増え、奇数の個数は一つおくれて進むのがわかります。
4（2段目）；偶数1個
8（3段目）；偶数1個、奇数1個
16（4段目）；偶数2個、奇数1個
32（5段目）；偶数3個、奇数2個
...
512（9段目）；偶数21個、奇数13個
で34個とわかります。

お礼

ポイントがつかめました。ありがとうございます。

回答No.2

rtz

2進数で考えると楽です。

回答No.1

Quattro99

奇数の場合は1を足すんですね？

さかのぼって考えていけばよいのでは？