PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 151 / 規格寸法用紙 : 期待値問題

ある印刷屋では毎週16回の定期的な仕事がある。毎回,A5サイズの特殊な色校正用紙を1枚使う。

月曜日の朝に主任はA1サイズの特殊紙が入った新しい封筒を開ける。

彼はA1の紙を半分に切る。するとA2の紙が2枚できる。片方を半分に切るとA3の紙が2枚できる。以下,A5の紙を得るまで繰り返し,1枚をその週の最初の仕事に使う。使われなかった紙はすべて元の封筒に戻す。

f:id:variee:20170903203403g:plain

各仕事の際に主任は封筒からランダムに紙を1枚取り出す。A5の紙を取り出したなら,そのまま仕事に使う。そうでない場合は半分に切ることを繰り返し,A5の紙を1枚使って残りは元の封筒に戻す。

週の最初と最後の仕事以外で封筒に紙が1枚だけ入っている回数の期待値を求めよ。四捨五入して小数点以下6桁で答えること (x.xxxxxxという形)。

Problem 151 - Project Euler


各用紙の枚数の組を (a2, a3, a4, a5) で表します。
1回目の作業が終わった後の状態は (1, 1, 1, 1)で,この後は次のような操作の繰り返しです。

  • 操作1:ある用紙を1枚減らす
  • 操作2:その用紙より小さい用紙を1枚ずつ増やす

各用紙の枚数の変化を追ってもらちがあかないので,「ない用紙は減らせない」「A5の紙に対しては操作2がない」に注意して期待値の漸化式を立式します。