横浜市立大学
2014年 医学部 第4問
4
![nを4以上の整数とする.1番からn番までの番号がふられたボールが1つずつある.このとき,以下の問いに答えよ.(1)以下のような操作でボールを1列に並べる:(i)1番のボールを適当な位置におく.(ii)2番のボールを1番のボールの左または右に同じ確率でおく.(iii)3番のボールをすでに並んでいる2つのボールの左または間または右に同じ確率でおく.\mon[\tokeishi]以下n番まで番号順に,k番のボールを,すでに並んでいるボールの一番左または間または一番右に同じ確率でおく,ことを繰り返す.例えば,左から2番,1番,3番のボールが並んでいるとき,4番のボールが2番と1番の間におかれる確率は1/4である.n番のボールをおき終えたとき,i番のボールが左からj番目に並ぶ確率は1/nであることを証明せよ.ただし,iとjは1以上,n以下の整数とする.(2)(1)のボールの列を,(左から)番号順に並び替えるため,以下の操作を考える:隣り合った2つのボールの組で,左のボールの番号が右のそれより大きなもの(入れ替え可能な組と呼ぶ)が存在するとき,そのようなボールの組を1つ選び,入れ替える.入れ替え可能な組が複数あった場合に,入れ替える組をどのように選んだとしても,この操作を繰り返すことにより,すべてのボールの列は,必ず番号順の列になることを証明せよ.(3)(2)の操作の回数は,入れ替える組の選び方とは無関係であることを証明せよ.(4)(2)においてボールの列を番号順に並べ替えるとき,i番のボールを,より番号の小さいボールと入れ替える回数の期待値をE_iとする.このとき,Σ_{i=1}^nE_iを求めよ.](./thumb/308/2359/2014_4.png)
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 \] を求めよ.
類題(関連度順)
![](./thumb/683/2949/2013_1s.png)
![](./thumb/472/849/2010_6s.png)
![](./thumb/202/95/2016_1s.png)
![](./thumb/683/2949/2011_3s.png)
![](./thumb/179/909/2010_3s.png)
![](./thumb/608/2733/2012_1s.png)
![](./thumb/695/923/2012_4s.png)
![](./thumb/608/2732/2012_1s.png)
![](./thumb/464/2631/2013_2s.png)
コメント(0件)
現在この問題に関するコメントはありません。
書き込むにはログインが必要です。