Evolton

名古屋大学 2014年度 前期日程 第2次学力試験理系数学 第4問

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

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

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

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

(*) 数列{an}のある項がmとなる確率が1100以下となる。

難易度6/ 10計算量6/ 10目安24分

整数、数列、確率 範囲評価、場合分け、数え上げ

方針

まず帰納法で an=[N/2n−1] を示す。ある項が m になる条件は、ある j=n−1 について m2j≦N<(m+1)2j となることである。(1)(2) はこの区間を直接数える。(3) は m が 2q≦m<2q+1 を満たすとき、該当する N が 2100−q−1 個であることを使う。確率が 1/100 以下になる最小の q を決め、最小の m を選ぶ。

解答

(1)

まず、すべての正の整数 n について an=[N2n−1] であることを確認する。n=1 では a1=N なので成り立つ。an=[N/2n−1] とするとan+1=[an2]=[12[N2n−1]]=[N2n]である。よって帰納的に成り立つ。

したがって a3=1 は [N4]=1 と同値である。これは 1≦N4<2 すなわち 4≦N<8 を意味する。N は整数なので N=4,5,6,7 である。

(2)

ある項が2になるとは、ある整数 j≧0 について [N2j]=2 となることである。これは 2≦N2j<3 すなわち 2j+1≦N<3⋅2j と同値である。 0≦N<210 なので、可能な j は j=0,1,2,…,8 である。各 j について、整数 N の個数は 3⋅2j−2j+1=2j 個である。また、これらの区間は互いに重ならない。したがって求める個数は ∑j=082j=29−1=511 である。

(3)

正の整数 m を固定する。ある項が m になる条件は、ある整数 j≧0 について [N2j]=m となることである。これは m2j≦N<(m+1)2j である。

ここで 2q≦m<2q+1 となる整数 q≧0 をとる。0≦N<2100 の範囲で上の条件を満たす N は、j=0,1,…,99−q についてそれぞれ 2j 個ずつある。実際、j=99−q までなら (m+1)2j≦2q+1299−q=2100 であり、j=100−q では m2j≧2q2100−q=2100 となって範囲外である。

したがって、ある項が m となる N の個数は ∑j=099−q2j=2100−q−1 である。よってその確率は 2100−q−12100 である。

これが 1/100 以下となる最小の m を求める。q=6 のとき294−12100>294−2872100=1278192>1100である。一方、q=7 のとき293−12100<1128<1100である。したがって必要な最小の q は7である。 q=7 を満たす最小の正の整数 m は m=27=128 である。よって求める最小の正の整数は 128 である。

別解

解法2(二進法)

方針

[an/2] は二進法表示の末尾1桁を消す操作である。この見方で (1) は先頭が1の3桁、(2) は先頭が10の高々10桁、(3) は m の二進法表示を接頭部にもつ整数を数える。

解答

an+1=[an/2] は、非負整数の二進法表示から末尾の1桁を消す操作である。

(1) a3=1 であるためには、N の二進法表示から末尾2桁を消した結果が 1 になればよい。したがってN=(100)2,(101)2,(110)2,(111)2,すなわちN=4,5,6,7である。

(2) ある項が2、すなわち (10)2 になるためには、N の二進法表示が 10 で始まればよい。全体の桁数が j+2 桁なら、その後ろの j 桁は自由なので 2j 個ある。N<210 より 0≦j≦8 だから、個数は∑j=082j=29−1=511である。

(3) 2q≦m<2q+1 とすると、m の二進法表示は q+1 桁である。数列のある項が m になる N は、m の二進法表示の後ろに j 桁を自由につけたものである。N<2100 より 0≦j≦99−q なので、その個数は∑j=099−q2j=2100−q−1.したがって確率は2100−q−12100.q=6 では294−12100>1278192>1100,q=7 では293−12100<1128<1100.よって必要な最小の桁区分は q=7 であり、その範囲の最小の正整数はm=27=128である。

総評

難度6、計算量6。目安時間は24分。床関数の反復を、N を2で割って整数部分を取る操作、すなわち2進法で末尾を消す操作として捉えるのが核心である。(1)(2) は区間を直接数えればよいが、(3) は m の2進法の桁数だけで個数が決まることに気づくと整理しやすい。確率の比較では近似で済ませず、q=6 ではまだ大きく、q=7 で初めて 1/100 以下になることを不等式で示す必要がある。 本文内の二進法による見方を全小問を含む独立答案へ分離し、確率比較を簡潔な厳密不等式へ整理した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る名大の整数の問題で問題集を作る

出典: 名古屋大学 2014年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。