やがてペレドゥルは川の流れる谷にやってきた. そのへりには木々が生い茂り, 川の両岸には平らな牧草地があった.
そしてこちらの岸には白い羊の群れ, 向こう岸には黒い羊の群れがいた.
白い羊の一匹がメェと鳴くと, 黒い羊の一頭が川を渡って, 白い羊となった.
黒い羊の一匹がメェと鳴くと, 白い羊の一頭が川を渡って, 黒い羊となった.
(「マビノギオン」 エヴラウグの息子ペレドゥルの物語より)
初期状態として, 黒い羊 n 頭の群れと白い羊 n 頭の群れが存在する.
羊全体の中からランダムで一頭が相手の群れに呼びかけ, 呼びかけられた群れの羊が一頭だけ色を変えて呼ばれた群れに合流する.
この合流のあと, ペレドゥルは任意の数の白羊を除去してよい. 彼の目標は最後に残った黒羊の数を最大化することである.
うまく最大化できる戦略をとったときの, 最後の黒羊の期待値をE(n)とする.
E(5) = 6.871346 であることがわかっている (小数点下6桁になるよう四捨五入してある)
E(10000)を求めよ (同様に小数点下6桁になるよう四捨五入すること)