漸化式の視覚化【視覚的な意味と操作の意味を考える】【2015年度京都大学】

問題はこちら（画像をクリックするとPDFファイルで開きます。）

$\displaystyle \frac{1}{2}$ からスタートし、２種類の関数を用いて次々と値を出して数列を作っていくという操作について考えます。

京大らしく、シンプルな問題ですが簡単ではありません。

これまた京大の特徴の一つである「誘導がない」形式での出題なので、構想から自分で組み立てる必要があります。

（以下ネタバレ注意）

+ クリック（タップ）して続きを読む

この数列の振る舞いをどう捉えるか

簡単な実験をしてみても、中々核心まで辿り着けないでしょう。

問題の匂いから確率漸化式を疑うことはできるかもしれませんが、２種類の関数について、どのタイミングでどちらを使うかを追っていくことが大変なので頭を抱えてしまう人も多いでしょう。

この数列がどのような振る舞いをするかを視覚的に捉えてみます。

$a_{n+1}=f(a_{n})$ で定まる数列の視覚化

ある関数 $f(x)$ を用いて

$a_{n+1}=f(a_{n})$

と「代入して次、代入して次、$\cdots$」と定まっていく数列の振る舞いを目で見ると、次の図のようになります。

代入して得た値は、「縦軸」の値となります。

次の代入に備え、縦軸の値を「横軸」にもっていくためには

$y=x$ ( 横軸の値と縦軸の値が等しくなるようなライン )

を書き添えることで解決します。

本問の場合

本問の漸化式を司る関数は２種類ありますので、若干図がうるさくなりますが、本問の数列の振る舞いを視覚化すると以下のようになります。

こうしてみると、$\displaystyle \frac{2}{3}$ という値のほかに、キーとなる数値である $\displaystyle \frac{1}{3}$ という数字に辿り着きます。

恐らく多くの人が漸化式を立てる際

$x_{n} \lt \displaystyle \frac{2}{3}$ となる確率を $P_{n}$ とする。

という、本問の問題文で設定されているものを単純にそのまま運用しようとして困ってしまったのではないかと思います。

困るのは当然で、この $\displaystyle \frac{1}{3}$ というキーナンバーに辿り着き

$0\lt x_{n} \lt \displaystyle \frac{1}{3}$ となる状態
$\displaystyle \frac{1}{3} \leq x_{n} \lt \displaystyle \frac{2}{3}$ となる状態
$\displaystyle \frac{2}{3} \leq x_{n} \lt 1$ となる状態

という３種類の状態推移を考える必要があるわけです。

そこで、

$0\lt x_{n} \lt \displaystyle \frac{1}{3}$ となる状態を $A_{n}$
$\displaystyle \frac{1}{3} \leq x_{n} \lt \displaystyle \frac{2}{3}$ となる状態を $B_{n}$
$\displaystyle \frac{2}{3} \leq x_{n} \lt 1$ となる状態を $C_{n}$

と設定し、

状態 $A_{n}$ , $B_{n}$ , $C_{n}$ となる確率をそれぞれ

$a_{n}$ , $b_{n}$ , $c_{n}$

とします。

状態推移を視覚化

$0\lt x_{n} \lt \displaystyle \frac{1}{3}$ からの状態推移

この図から分かる通り、状態 $A_{n}$ からは

確率 $\displaystyle \frac{1}{2}$ で状態 $A_{n+1}$
確率 $\displaystyle \frac{1}{2}$ で状態 $B_{n+1}$

となります。

$\displaystyle \frac{1}{3} \leq x_{n} \lt \displaystyle \frac{2}{3}$ からの状態推移

この図から分かる通り、状態 $B_{n}$ からは

確率 $\displaystyle \frac{1}{2}$ で状態 $A_{n+1}$
確率 $\displaystyle \frac{1}{2}$ で状態 $C_{n+1}$

となります。

$\displaystyle \frac{2}{3} \leq x_{n} \lt 1$ からの状態推移

この図から分かる通り、状態 $C_{n}$ からは

確率 $\displaystyle \frac{1}{2}$ で状態 $B_{n+1}$
確率 $\displaystyle \frac{1}{2}$ で状態 $C_{n+1}$

となります。

漸化式の立式

状態推移を捉えることができれば

$$\begin{eqnarray}
\left\{
\begin{array}{l}
a_{n+1} = \displaystyle \frac{1}{2} a_{n}+\displaystyle \frac{1}{2} b_{n} \\
b_{n+1} = \displaystyle \frac{1}{2} a_{n}+\displaystyle \frac{1}{2} c_{n} \\
c_{n+1} = \displaystyle \frac{1}{2} b_{n}+\displaystyle \frac{1}{2} c_{n} \\
\end{array}
\right.
\end{eqnarray}$$

という連立漸化式が立式できます。

この立式ができれば、あとは漸化式の処理となります。

連立漸化式の基本は文字消去ですが、確率漸化式特有の隠れた条件

$a_{n}+b_{n}+c_{n}=1$

をうまいこと活用して処理していくことも、この分野では必要な力です。

漸化式の処理そのものについては、以下のシリーズも適宜活用してください。

テーマ別演習：漸化式の解法基本パターン

漸化式の解法基本パターン　第１講【２項間漸化式：ズラせば等比数列】

問題はこちら（画像をクリックするとPDFファイルで開きます。）漸化式は問題を解く中で処理しなければならない場面が多々あります。確率漸化式などの確率や場合の数の分野との融合点列など、座標との融合整数問題との融合など、漸化式は道具として使う場面が多々あります。漸化式が立式できても、それが解けないとなると意味がありませんから、基本的な漸化式についてはきちんと処理できる必要があります。そこで基本的な漸化式について一通りこのシリーズで押さえておきたいと思いますこのシリーズの一覧はこちら ...

漸化式の解法基本パターン　第２講【２項間漸化式：心霊写真型】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら前回の第１講で扱った Type 1 $a_{n+1}=pa_{n}+q$ ( $p \neq 1$ ) の派生形として今回は Type 2 (心霊写真型) $a_{n+1}=pa_{n}+q^{n}$ ( $p \neq 1$ ) ( $q$ の肩になんか乗ってる ) というタイプを扱います。この心霊写真型の除霊の仕方は２パターンあり心霊写真型の除霊の仕方 ...

漸化式の解法基本パターン　第３講【２項間漸化式：分数型】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら漸化式基本パターン第３講では、「分数型」の漸化式を扱います。まずは分数型の中でも簡単な形（特殊な形）である分数漸化式（メタボ型） $a_{n+1}=\displaystyle \frac{ra_{n}}{pa_{n}+q}$ を考えます。分数の形がなんとなく△の形をしており、引き締まっておりません。逆数を取ると \(\displaystyle \frac{1}{a_{n+1}}=\disp ...

漸化式の解法基本パターン　第４講【２項間漸化式：特性方程式使うと事故る型】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら漸化式の解法基本パターン第４講では特性方程式使うと事故る型 $a_{n+1}=pa_{n}+An+B$ というタイプをやっていきます。長ったらしいネーミングですが、逆に一回事故った方が理解が深まると思います。（もっといいネーミングがあれば募集します。）文字のままやっててもピンとこないかもしれませんので、本問の (1) を例にとって、敢えて事故ってみます。誤答 ...

漸化式の解法基本パターン　第５講【２項間漸化式：そうだ、logをとろう型】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら漸化式の解法基本パターン第５講ではそうだ、log をとろう型 $a_{n+1}^{p}=Aa_{n}^{q}$ というタイプを扱います。両辺底が $A$ の対数をとると $p\log_{A}a_{n+1}=q\log_{A}a_{n}+1$ となり、$b_{n}=\log_{A}a_{n}$ とおくと \(b_{n+1}=\displaystyle \frac{q}{p}b_{n} ...

漸化式の解法基本パターン　第６講【２項間漸化式：変数倍型】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら第６講では「変数倍」型を扱います。変数倍型 $$a_{n+1}=f(n)a_{n}+A$$ 基本的に$a_{n+1}=pa_{n}+\cdots$ という「定数倍」であれば、多少のイレギュラーこそあれど、等比数列としての処理に帰着することになります。今回のように「変数倍」になってくると、形一つで対応が変わってきます。このあたりを体系的にまとめるのは難しいでしょう。 (1) , (2) は ...

漸化式の解法基本パターン　第７講【隣接３項間漸化式への対応】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら第７講では３項間漸化式を扱います。３項間漸化式 $$a_{n+2}+pa_{n+1}+qa_{n}=0$$ この３項間漸化式の狙い筋は狙い筋 $$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_{n})$$ という形に変形することで、等比数列の形として処理することです。つまり、 \(a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1 ...

漸化式の解法基本パターン　第８講【２種類の連立漸化式への対応】

問題はこちら（画像をクリックするとPDFファイルで開きます。）このシリーズの一覧はこちら第８講では「連立漸化式」を扱います。連立漸化式の代表的な解法としては２つあります。連立漸化式の代表的方針１文字消去上手い倍率を見つけて辺々操作それぞれについて見てみます。１文字消去路線について今回の (1) を例にとってみます。消しやすい第２式に注目すれば、$a_{n}=b_{n+1}-b_{n}$ と見ることができます。第１式に代入するために番号を 1 つ上げれば ...

本問の操作的意味

今回の問題で扱っている２つの関数

$f_{0}(x)=\displaystyle \frac{x}{2}$ , $f_{1}(x)=\displaystyle \frac{x+1}{2}$

について考えてみます。

$f_{0}$ というのは、持ち込まれた $x$ という値を

$2$ で割る

という操作です。

同様に$f_{1}$ というのは、持ち込まれた $x$ という値を

$1$ を加えてから、$2$ で割る

という操作です。

「$2$ で割る」という操作の意味は、$2$ 進法で考えると明確な意味があり、

２進数表示された数の「小数点を左に１個ずらす」

という意味があります。

普段 $10$ 進法を使っている我々からすれば、$10$ で割れば小数点が左に１個ズレるのを想像すればよいでしょう。

では、「$1$ を加えてから、$2$ で割る」という操作の意味はどうでしょうか？

ぜひ考えてみましょう。

【総括】のあとに【参考】という項目を立ててこのことに触れてあります。

解答はコチラ

漸化式の視覚化【視覚的な意味と操作の意味を考える】【2015年度京都大学】

問題はこちら（画像をクリックするとPDFファイルで開きます。）

この数列の振る舞いをどう捉えるか

\(a_{n+1}=f(a_{n})\) で定まる数列の視覚化

本問の場合

状態推移を視覚化

\(0\lt x_{n} \lt \displaystyle \frac{1}{3}\) からの状態推移

\(\displaystyle \frac{1}{3} \leq x_{n} \lt \displaystyle \frac{2}{3}\) からの状態推移

\(\displaystyle \frac{2}{3} \leq x_{n} \lt 1\) からの状態推移

漸化式の立式

本問の操作的意味

漸化式の視覚化【視覚的な意味と操作の意味を考える】【2015年度 京都大学】

問題はこちら（画像をクリックするとPDFファイルで開きます。）

この数列の振る舞いをどう捉えるか

\(a_{n+1}=f(a_{n})\) で定まる数列の視覚化

本問の場合

状態推移を視覚化

\(0\lt x_{n} \lt \displaystyle \frac{1}{3}\) からの状態推移

\(\displaystyle \frac{1}{3} \leq x_{n} \lt \displaystyle \frac{2}{3}\) からの状態推移

\(\displaystyle \frac{2}{3} \leq x_{n} \lt 1\) からの状態推移

漸化式の立式

本問の操作的意味

漸化式の視覚化【視覚的な意味と操作の意味を考える】【2015年度京都大学】