逆から考える。
すなわち、すべて見終わった状態から考える。
状態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)
が求める最適値となる。