第３４問の解答

１．問題　［場合の数］

ある整数に対して、それが偶数の場合は２で割り、奇数ならば１を足します。
そして、この操作を結果が１になるまで続けます。
例えば６は、６→３→４→２→１と４回の操作で１になります。
１０回の操作で１になる整数は全部で５５個あり、
その中の２１個が奇数であることが分かっています。（注１）
では、１２回の操作で１になる整数は全部で何個ありますか。

（注１） 奇数：２１個
35,37,41,49,79,87,91,93,103,107, 109,115,117,121,191,223,239,247,251,253, 511

偶数：３４個
34,72,76,78,84,86,90,100,102,106, 114,160,176,184,188,190,208,216,220,222, 232,236,238,244,246,250,384,448,480,496, 504,508,510,1024

２．解答例１

　１回の操作で、
結果が偶数：（例）３→４（奇数→偶数）、８→４（偶数→偶数）の２とおり、
結果が奇数：（例）６→３（偶数→奇数）の１とおりがある。・・・・（＊＊）

　同様に、２回の操作では、
結果が偶数：（例）６→３→４（偶数→奇数→偶数）、１６→８→４（偶数→偶数→偶数）、 ７→８→４（奇数→偶数→偶数）の３とおり、
結果が奇数：（例）１２→６→３（偶数→偶数→奇数）、５→６→３（奇数→偶数→奇数）の２とおりある。

　従って、１２回の操作で１になる整数は、
最初の２回の操作で結果が偶数：３＊３４＝１０２個
最初の２回の操作で結果が奇数：２＊２１＝　４２個、合計１４４個である。


３．解答例２

　ｎ回の操作で１になる偶数の個数をａn、奇数の個数をｂn、合計をｃnとおく。

　ｎ＞２のとき、上記（＊＊）より、

　　ａn+1＝ａn＋ｂn＝ｃn、 　　ｂn+1＝ａnとなり、
　従って、ａn+2＝ａn+1＋ａnとなって、ａn、ｂn、ｃnは、それぞれフィボナッチ数列となる。

容易に、ａ1＝１（２）、ｂ1＝０、ｃ1＝１（２）、 ａ2＝１（４）、ｂ2＝０、ｃ2＝１（４）、 ａ3＝１（８）、ｂ3＝１（３）、ｃ3＝２（８、３）が分かるので、
　ａn＝１，１，１，２，３，５，　８，１３，２１，３４，５５，　８９
　ｂn＝０，０，１，１，２，３，　５，　８，１３，２１，３４，　５５
　ｃn＝１，１，２，３，５，８，１３，２１，３４，５５，８９，１４４ となる。

４．全ての整数が１に到達することの証明

方法１：数学的帰納法

仮定１：ｎ＝１のときは既に１であり、ｎ＝２のとき、２→１である。

仮定２：ｎ≦2*m（m≧1）のとき、１に到達すると仮定する。
ｎ＝2*m-1のとき、ｎ→n+1＝2*mなので、ｎ=2*mの場合を調べれば良い。
ｎ＝2*mのとき、1<m<nなので、ｎ→ｍ→・・・→１。よって、ｎも１に到達する。

以上のことから、帰納法により、全ての正整数について、１に到達することが分かる。

　以上

方法２：背理法

もし、１に到達しない整数が存在したとする。このような整数のうち最小のものをｎとする。
明らかに、n>３。
ｎが偶数とすると、m=n/2は整数でm>n、かつn→m→・・・→１となり、ｎが最小に矛盾する。
ｎが奇数とすると、m=(n+1)，k＝m/2は整数でn>k、かつｎ→m→k→・・・→１となり、 ｎが最小に矛盾する。

　以上

方法３：単調数列

ｎを任意の正整数とする。

ｎから始めまる連鎖ｎ→・・・に出てくる整数の中から、数列ａk、(k=1,2,・・・)を次のように定義する。

まず、ａ1＝ｎとする。

次に、ｎ：奇数のとき、ｎ→（n+1)→(n+1)/2→・・・なので、ａ2＝(ｎ＋１)/2　とする。ａ1＞ａ2＞０。

　　　ｎ：偶数のとき、ｎ→n/2→・・・なので、ａ2＝ｎ/2　とする。ａ1＞ａ2＞０。

同様にして、ａ3、ａ4・・・を定義する。

このようにして定義した整数の数列ａkは、単調に減少するが、常に正だから、有限個であり、最小値ｍが存在する。

もし、ｍ＞１とすれば、上記方法でｍより小さい数ｐがあり、ｍ→ｐとなるので、ｍが最小であることと矛盾する。

よって、最小値は１となり、ｎから始まる連鎖は１に到達することが示された。

　以上