割り箸 (手遊びゲーム)
問題は、負けたプレイヤーがちょうどターンを行ったプレイヤーとなっていることである。プレイヤーは自身のターンで負けることはできないため、これらの状態は明らかに到達不可能である。
到達不可能な状態のうちの r − 2 {\displaystyle r-2} 個は、ターンプレイヤーが 0 < k < r − 1 {\displaystyle 0<k<r-1} なる値 k {\displaystyle k} の手を h {\displaystyle h} 個もち、もう一方のプレイヤーは値 k {\displaystyle k} の生きている手を1つだけ持つ状態である。ターンを行った値 k {\displaystyle k} の生きている手を1つだけもつプレイヤーは、直前のターンで分割は行えず、それゆえそのプレイヤーは自身のただ1つの生きている手[00...0k]を用いて攻撃したことになるが、相手を [00...0k]を用いて攻撃した結果相手が値 k {\displaystyle k} の手を h {\displaystyle h} 個もつためには、死んだ手に攻撃しなければならないため、これは不可能である。したがって、この状態には到達不可能である。
到達不可能な状態のうちの h − 1 {\displaystyle h-1} 個は、ターンプレイヤーが値 r − 1 {\displaystyle r-1} の手を h {\displaystyle h} 個もち、もう一方のプレイヤーが値 r − 1 {\displaystyle r-1} の生きている手を k {\displaystyle k} 個(それ以外の手はすべて死んだ手)もつ状態である(ただし 0 < k < h − 1 {\displaystyle 0<k<h-1} )。
ロールオーバー量が5、手の数が2である場合。
2人のプレイヤーでは、204個の到達可能状態がある。
3人のプレイヤーでは、3337個の到達可能状態がある。
4人のプレイヤーでは、25000個以上の到達可能状態がある。