横浜市立大学
2014年 医学部 第4問
4
4
$n$を$4$以上の整数とする.$1$番から$n$番までの番号がふられたボールが$1$つずつある.このとき,以下の問いに答えよ.
(1) 以下のような操作でボールを$1$列に並べる:
(ⅰ) $1$番のボールを適当な位置におく.
(ⅱ) $2$番のボールを$1$番のボールの左または右に同じ確率でおく.
(ⅲ) $3$番のボールをすでに並んでいる$2$つのボールの左または間または右に同じ確率でおく. [$\tokeishi$] 以下$n$番まで番号順に,$k$番のボールを,すでに並んでいるボールの一番左または間または一番右に同じ確率でおく,ことを繰り返す.
例えば,左から$2$番,$1$番,$3$番のボールが並んでいるとき,$4$番のボールが$2$番と$1$番の間におかれる確率は$\displaystyle \frac{1}{4}$である.
$n$番のボールをおき終えたとき,$i$番のボールが左から$j$番目に並ぶ確率は$\displaystyle \frac{1}{n}$であることを証明せよ.ただし,$i$と$j$は$1$以上,$n$以下の整数とする.
(2) $(1)$のボールの列を,(左から)番号順に並び替えるため,以下の操作を考える:
隣り合った$2$つのボールの組で,左のボールの番号が右のそれより大きなもの(入れ替え可能な組と呼ぶ)が存在するとき,そのようなボールの組を$1$つ選び,入れ替える.
入れ替え可能な組が複数あった場合に,入れ替える組をどのように選んだとしても,この操作を繰り返すことにより,すべてのボールの列は,必ず番号順の列になることを証明せよ.
(3) $(2)$の操作の回数は,入れ替える組の選び方とは無関係であることを証明せよ.
(4) $(2)$においてボールの列を番号順に並べ替えるとき,$i$番のボールを,より番号の小さいボールと入れ替える回数の期待値を$E_i$とする.このとき, \[ \sum_{i=1}^n E_i \] を求めよ.
(1) 以下のような操作でボールを$1$列に並べる:
(ⅰ) $1$番のボールを適当な位置におく.
(ⅱ) $2$番のボールを$1$番のボールの左または右に同じ確率でおく.
(ⅲ) $3$番のボールをすでに並んでいる$2$つのボールの左または間または右に同じ確率でおく. [$\tokeishi$] 以下$n$番まで番号順に,$k$番のボールを,すでに並んでいるボールの一番左または間または一番右に同じ確率でおく,ことを繰り返す.
例えば,左から$2$番,$1$番,$3$番のボールが並んでいるとき,$4$番のボールが$2$番と$1$番の間におかれる確率は$\displaystyle \frac{1}{4}$である.
$n$番のボールをおき終えたとき,$i$番のボールが左から$j$番目に並ぶ確率は$\displaystyle \frac{1}{n}$であることを証明せよ.ただし,$i$と$j$は$1$以上,$n$以下の整数とする.
(2) $(1)$のボールの列を,(左から)番号順に並び替えるため,以下の操作を考える:
隣り合った$2$つのボールの組で,左のボールの番号が右のそれより大きなもの(入れ替え可能な組と呼ぶ)が存在するとき,そのようなボールの組を$1$つ選び,入れ替える.
入れ替え可能な組が複数あった場合に,入れ替える組をどのように選んだとしても,この操作を繰り返すことにより,すべてのボールの列は,必ず番号順の列になることを証明せよ.
(3) $(2)$の操作の回数は,入れ替える組の選び方とは無関係であることを証明せよ.
(4) $(2)$においてボールの列を番号順に並べ替えるとき,$i$番のボールを,より番号の小さいボールと入れ替える回数の期待値を$E_i$とする.このとき, \[ \sum_{i=1}^n E_i \] を求めよ.
類題(関連度順)
コメント(0件)
現在この問題に関するコメントはありません。
書き込むにはログインが必要です。