次のゲームは, 組み合わせゲーム理論の古典的な例である:
2人のプレイヤーが, 一列に並んだ n 個の白い正方形から開始して, 交互にターンを行う.
各ターンでは, プレイヤーは2つの隣り合う白い正方形を選び, 黒で塗る.
最初に色を塗ることができなくなったプレイヤーが負けとなる.
したがって, 1≦n≦5 に対し, 先手必勝となる n の値は 3 個ある.
同様に, 1≦n≦50 に対し, 先手必勝となる n の値は 40 個ある.
1≦n≦1 000 000 に対し, 先手必勝となる n の値は何個あるか.