宝箱(4)

逆から考える。
すなわち、すべて見終わった状態から考える。
状態sに対し、
すべて見終わった状態になるまでにかかる回数の期待値を

E(s)

と書く。
すべて見終わった状態を、

111 111 111

と表記し、
最初の状態を、

000 000 000

と表記する。
左から箱1,箱2,箱3として、
その中で左からアイテム1,アイテム2,アイテム3のフラグとする。
アイテム1だけすでに見ていれば、

100

とする。
まず、

E(111 111 111) = 0

となる。
あと残り1つのときは、
最後の1つが出る確率は1/3だから、
例えば、

E(111 111 110) = 3

となる。
これと対称の状態も同じである。


同様に考えて、

E(111 111 100) = 3/2 + E(111 111 110) = 9/2
E(111 110 110) = 3/2 + E(111 111 110) = 9/2
E(111 101 110) = 2 + E(111 111 110) = 5

次にセットするアイテムの組合せ6通りのうち、
最初の2つは4通りで、
最後のは3通りで次の状態に移行できるので、
移行する回数の期待値はそれぞれ3/2、2となる。


次に、
状態 101 110 110
を考える。
このときに、それぞれの箱のアイテム番号が、
123 のとき 101 110 111 に移行
132 のとき 101 111 110 に移行
213 のとき 111 110 110 か 101 110 111 に移行可能だが、
E(111 110 110) = 9/2、E(101 110 111) = 5
だから、111 110 110 に移行する(最適な箱の選択)。
231 のときも同様に考えて 111 110 110 に移行
312 321 のときは移行できない。


まとめると、
123 : E(101 110 111) = 5
132 : E(101 111 110) = 5
213 : E(111 110 110) = 9/2
231 : E(111 110 110) = 9/2
312 : ×
321 : ×


次の状態に移行する確率は2/3だから、
平均3/2回で次に移行する。
だから、

E(101 110 110) = 3/2 + (5 + 5 + 9/2 + 9/2) / 4 = 25/4


このように、
最後から、フラグ本数が多い順にE(s)を計算していき、
最後に計算される

E(000 000 000)

が求める最適値となる。