戻る
032 平成26年度前期  名古屋大学   理系 ・・・ 数列と確率(数学AB)  難

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


名古屋大学 前期理系(2014)

 負でない整数Nが与えられたとき、a1=N、an+1=[a/2] (n=1、2、3、・・・)として数列
{a}を定める。ただし、[a]は実数aの整数部分(k≦a<k+1となる整数k)を表す。

(1) a3=1となるようなNをすべて求めよ。

(2) 0≦N<210をみたす整数Nのうちで、Nから定まる数列{a}のある項が2となるような
  ものはいくつあるか。

(3) 0から2100−1までの2100個の整数から等しい確率でNを選び、数列{a}を定める。
  次の条件(*)をみたす最小の正の整数mを求めよ。

  (*) 数列{a}のある項がmとなる確率が1/100以下となる。


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

N=1のとき、出来る数列は、 1,0,0,・・・
N=2のとき、出来る数列は、 2,1,0,・・・
N=3のとき、出来る数列は、 3,1,0,・・・
N=4のとき、出来る数列は、 4,2,1,0,・・・
N=5のとき、出来る数列は、 5,2,1,0,・・・
N=6のとき、出来る数列は、 6,3,1,0,・・・
N=7のとき、出来る数列は、 7,3,1,0,・・・
N=8のとき、出来る数列は、 8,4,2,0,・・・
  ・・・・・・・・・・・・・・・・・・・・・・・・・・

 上記の計算から、求める解は、N=4、5、6、7 であることが直ぐ分かる。

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

(解) (1) a3=1 より、 [a2/2]=1 すなわち、 1≦a2/2<2 から、 2≦a2<4

      よって、 a2=2、3

     a2=2 のとき、同様にして、 4≦a1<6 より、 a1=4、5

     a2=3 のとき、同様にして、 6≦a1<8 より、 a1=6、7

      以上から、 N=a1=4、5、6、7  (終)


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

N=1のとき、 1 → 0
N=2のとき、 10 → 1 → 0
N=3のとき、 11 → 1 → 0
N=4のとき、 100 → 10 → 1 → 0
N=5のとき、 101 → 10 → 1 → 0
N=6のとき、 110 → 11 → 1 → 0
N=7のとき、 111 → 11 → 1 → 0
N=8のとき、 1000 → 100 → 10 → 1 → 0
 ・・・・・・・・・・・・・・・・・・・・・・・・

(解) (2) 0≦N<210をみたす整数Nを2進数展開して、Nから定まる数列{a}のある項
      が2となるようなものは、必ず、「10・・・・・」の形に書ける場合である。

 したがって、0から111・・・11(1が10個並ぶ)までの中で、「10・・・・・」の形に書けるもの
の個数を数えればよい。

 10**・・・* (*が8個並ぶ) のタイプの総数は、28=256個
 10**・・・* (*が7個並ぶ) のタイプの総数は、27=128個
 10**・・・* (*が6個並ぶ) のタイプの総数は、26=64個
 10**・・・* (*が5個並ぶ) のタイプの総数は、25=32個
 10**・・・* (*が4個並ぶ) のタイプの総数は、24=16個
 10**・・・* (*が3個並ぶ) のタイプの総数は、23=8個
 10**・・・* (*が2個並ぶ) のタイプの総数は、22=4個
 10**・・・* (*が1個) のタイプの総数は、21=2個
 10**・・・* (*が0個) のタイプの総数は、20=1個

 以上から、 256+128+64+32+16+8+4+2+1=511(個) となる。  (終)

(解) mを2進数展開したとき、r桁になるとする。すなわち、2r-1≦m<2

数列{a}のある項がmとなるということは、2r-1≦N≦2100−1 を満たさなければならない

ので、Nは、2100−2r-1個ある。

 数列{a}のある項がmとなるためには、最上位のr桁がmと一致すればよい。その個数

は、(2100−2r-1)/2r-1=2101-r−1である。

 よって、数列{a}のある項がmとなる確率は、 (2101-r−1)/2100 となる。

ここで、 (2101-r−1)/2100≦1/100 となるためには、 1/2r-1≦1/100+1/2100

右辺=0.01+0.000000000000000000000000000001=0.010000000000000000000000000001

なので、

r−1=0 のとき、 左辺=1
r−1=1 のとき、 左辺=1/2=0.5
r−1=2 のとき、 左辺=1/4=0.25
r−1=3 のとき、 左辺=1/8=0.125
r−1=4 のとき、 左辺=1/16=0.0625
r−1=5 のとき、 左辺=1/32=0.03125
r−1=6 のとき、 左辺=1/64=0.015625(>0.01)
r−1=7 のとき、 左辺=1/128=0.0078125(<0.01)

から、 r−1≧7 で、条件(*)を満たす最小のmの値は、m=27=128  (終)


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