ある印刷所ではある一連の仕事を周に16回行うが、その仕事では毎回A5サイズの特別なプルーフ用紙(注: 印刷物の仕上がりを確認するために使用する校正用の紙)が1枚必要である。
毎週月曜の朝、主任は新しいA1サイズのプルーフ用紙の入った包みを空ける。
主任はそれを半分に裁断し、A2サイズの用紙2枚とする。そのうち1枚を同様に半分にカットし、A3サイズの用紙2枚とする。この作業をA5サイズの用紙2枚を得るまで続けたら、そのうち1枚を最初の仕事に供する。
そして、使わなかった残りの紙はすべてまとめて元の包みに戻しておく。
それ以降の仕事を始める時、主任は包みからランダムに用紙を取り出す。もし取り出した用紙がA5サイズなら、それを仕事に用いる。A5よりも大きなサイズの用紙を取り出した際には、週の最初にやったのと同様に半分に裁断する作業を繰り返し、A5サイズの用紙を一枚仕事に用いて残りを包みに戻す。
週の最初の仕事と最後の仕事を除いて、包みの中に用紙1枚だけ入っているという状況に主任が遭遇する回数(一週間のうちで)の期待値を求めよ。
答えは小数点以下6桁に丸め、x.xxxxxxという形式で答えよ。
A2、A3、A4、A5の用紙の枚数を(a, b, c, d)というベクトルで表現する。また(a, b, c, d)のときの期待値をE(a, b, c, d)とする。
(a, b, c, d)から1枚選んだとすると、枚数は次のように変化する。
- aを選んだ: (a-1, b+1, c+1, d+1)
- bを選んだ: (a, b-1, c+1, d+1)
- cを選んだ: (a, b, c-1, d+1)
- dを選んだ: (a, b, c, d-1)
もしこの各々について期待値が計算できたなら、その期待値の平均をとれば(用紙の枚数で重み付けして場合の数で割る)E(a, b, c, d)が求められる。便宜的に上記の期待値をE(A), E(B), E(C), E(D)と書くと、
- E(a, b, c, d) = (E(A)*a + E(B)*b + E(C)*c + E(D)*d) / (a+b+c+d)
また、用紙の枚数が(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0)のどれかのとき、この時の期待値は各々1 + E(0, 1, 1, 1), 1+(0, 0, 1, 1), 1となることは容易にわかる。
そして(0, 0, 0, 1)ならば問題の定義から期待値0であり、仕事を繰り返せば16回目には必ずこの状態に行き着くので、再帰が使える。
next.s <- function(A, i){ if(i == 4) return(A - c(0,0,0,1)) A[i] <- A[i] - 1 A[(i+1):4] <- A[(i+1):4] + 1 A } calc.ex <- function(A){ if(any(A < 0)) return(0) if(all(A == c(0,0,0,1))) return(0) if(sum(A) == 1) return(Recall(next.s(A, (1:4)[as.logical(A)])) + 1) sum(c(Recall(next.s(A, 1)), Recall(next.s(A, 2)), Recall(next.s(A, 3)), Recall(next.s(A, 4))) * A) / sum(A) } calc.ex(c(1,1,1,1))
8.3秒だった。
