０３２	平成２６年度前期	名古屋大学	理系	・・・	数列と確率（数学ＡＢ）	難

　いつ終わるともしれない仕事の合間に、「難問」と評判の問題を覗いてみたくなった。どん
な問題かな？


名古屋大学　前期理系（２０１４）

　負でない整数Ｎが与えられたとき、ａ₁＝Ｎ、ａ_ｎ+1＝［ａ_ｎ/２］　（ｎ＝１、２、３、・・・）として数列
｛ａ_ｎ｝を定める。ただし、［ａ］は実数ａの整数部分（ｋ≦ａ＜ｋ＋１となる整数ｋ）を表す。

（１）　ａ₃＝１となるようなＮをすべて求めよ。

（２）　０≦Ｎ＜２¹⁰をみたす整数Ｎのうちで、Ｎから定まる数列｛ａ_ｎ｝のある項が２となるような
　　ものはいくつあるか。

（３）　０から２¹⁰⁰−１までの２¹⁰⁰個の整数から等しい確率でＮを選び、数列｛ａ_ｎ｝を定める。
　　次の条件（*）をみたす最小の正の整数ｍを求めよ。

　　（*）　数列｛ａ_ｎ｝のある項がｍとなる確率が１/１００以下となる。


　いくつか実験してみよう。

Ｎ＝１のとき、出来る数列は、　１，０，０，・・・
Ｎ＝２のとき、出来る数列は、　２，１，０，・・・
Ｎ＝３のとき、出来る数列は、　３，１，０，・・・
Ｎ＝４のとき、出来る数列は、　４，２，１，０，・・・
Ｎ＝５のとき、出来る数列は、　５，２，１，０，・・・
Ｎ＝６のとき、出来る数列は、　６，３，１，０，・・・
Ｎ＝７のとき、出来る数列は、　７，３，１，０，・・・
Ｎ＝８のとき、出来る数列は、　８，４，２，０，・・・
　　・・・・・・・・・・・・・・・・・・・・・・・・・・

　上記の計算から、求める解は、Ｎ＝４、５、６、７　であることが直ぐ分かる。

　これをもっともらしく書こうとすれば次のようになるであろう。

（解）　（１）　ａ₃＝１ より、　［ａ₂/２］＝１　すなわち、　１≦ａ₂/２＜２　から、　２≦ａ₂＜４

　　　　　　よって、　ａ₂＝２、３

　　　　　ａ₂＝２　のとき、同様にして、　４≦ａ₁＜６　より、　ａ₁＝４、５

　　　　　ａ₂＝３　のとき、同様にして、　６≦ａ₁＜８　より、　ａ₁＝６、７

　　　　　　以上から、　Ｎ＝ａ₁＝４、５、６、７　　（終）


　各Ｎを２進数展開してみると、問題の趣旨が見えてくる。

Ｎ＝１のとき、　１　→　０
Ｎ＝２のとき、　１０　→　１　→　０
Ｎ＝３のとき、　１１　→　１　→　０
Ｎ＝４のとき、　１００　→　１０　→　１　→　０
Ｎ＝５のとき、　１０１　→　１０　→　１　→　０
Ｎ＝６のとき、　１１０　→　１１　→　１　→　０
Ｎ＝７のとき、　１１１　→　１１　→　１　→　０
Ｎ＝８のとき、　１０００　→　１００　→　１０　→　１　→　０
　・・・・・・・・・・・・・・・・・・・・・・・・

（解）　（２）　０≦Ｎ＜２¹⁰をみたす整数Ｎを２進数展開して、Ｎから定まる数列｛ａ_ｎ｝のある項
　　　　　　が２となるようなものは、必ず、「１０・・・・・」の形に書ける場合である。

　したがって、０から１１１・・・１１（１が１０個並ぶ）までの中で、「１０・・・・・」の形に書けるもの
の個数を数えればよい。

　１０**・・・*　（*が８個並ぶ）　のタイプの総数は、２⁸＝２５６個
　１０**・・・*　（*が７個並ぶ）　のタイプの総数は、２⁷＝１２８個
　１０**・・・*　（*が６個並ぶ）　のタイプの総数は、２⁶＝６４個
　１０**・・・*　（*が５個並ぶ）　のタイプの総数は、２⁵＝３２個
　１０**・・・*　（*が４個並ぶ）　のタイプの総数は、２⁴＝１６個
　１０**・・・*　（*が３個並ぶ）　のタイプの総数は、２³＝８個
　１０**・・・*　（*が２個並ぶ）　のタイプの総数は、２²＝４個
　１０**・・・*　（*が１個）　のタイプの総数は、２¹＝２個
　１０**・・・*　（*が０個）　のタイプの総数は、２⁰＝１個

　以上から、　２５６＋１２８＋６４＋３２＋１６＋８＋４＋２＋１＝５１１（個）　となる。　　（終）

（解）　ｍを２進数展開したとき、ｒ桁になるとする。すなわち、２^ｒ-1≦ｍ＜２^ｒ

数列｛ａ_ｎ｝のある項がｍとなるということは、２^ｒ-1≦Ｎ≦２¹⁰⁰−１　を満たさなければならない

ので、Ｎは、２¹⁰⁰−２^ｒ-1個ある。

　数列｛ａ_ｎ｝のある項がｍとなるためには、最上位のｒ桁がｍと一致すればよい。その個数

は、（２¹⁰⁰−２^ｒ-1）/２^ｒ-1＝２^101-ｒ−１である。

　よって、数列｛ａ_ｎ｝のある項がｍとなる確率は、　（２^101-ｒ−１）/２¹⁰⁰　となる。

ここで、　（２^101-ｒ−１）/２¹⁰⁰≦１/１００　となるためには、　１/２^ｒ-1≦１/１００＋１/２¹⁰⁰

右辺＝0.01＋0.000000000000000000000000000001＝0.010000000000000000000000000001

なので、

ｒ−１＝０　のとき、　左辺＝１
ｒ−１＝１　のとき、　左辺＝１/２＝０．５
ｒ−１＝２　のとき、　左辺＝１/４＝０．２５
ｒ−１＝３　のとき、　左辺＝１/８＝０．１２５
ｒ−１＝４　のとき、　左辺＝１/１６＝０．０６２５
ｒ−１＝５　のとき、　左辺＝１/３２＝０．０３１２５
ｒ−１＝６　のとき、　左辺＝１/６４＝０．０１５６２５（＞０．０１）
ｒ−１＝７　のとき、　左辺＝１/１２８＝０．００７８１２５（＜０．０１）

から、　ｒ−１≧７　で、条件（*）を満たす最小のｍの値は、ｍ＝２⁷＝１２８　　（終）


（コメント）　この問題を現役の高校生が解ききるのは至難の技だろう。その意味で、「難」な
　　　　　　のかな？ただ、この問題を苦もなく解く高校生も実際には存在するのだろう。