ゲーム理論の問題
石の山が つあり、山 A には 個、山 B には 個、山 C には 個の石がある。2 人のプレイヤーが交互に、どれか つの山を選び、その山から 個以上の好きな個数の石を取り除く（山にある個数まで取れる）。最後の石を取ったプレイヤーの勝ちとする（動かせなくなったプレイヤーの負け）。
この局面で先手が必勝となる最初の手はただ 通りである。その手を打った直後の山 A、山 B、山 C の石の個数を、この順に組で答えよ。
この問題で使うもの
- ニムとニム和（説明と入口の問題）
この問題を解けるようになるまで（8 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
ニムの必勝判定には、各山の個数を 2 進法で表して排他的論理和（ニム和）をとる方法を使います。ニム和が 0 の局面を相手に渡せば勝てます。
ヒント 2
全体のニム和を とすると、個数 の山を 個に変えれば全体のニム和は になります。ただし でないと石を取る手になりません。
ヒント 3
, , より、ニム和は です。各山について を計算し、 より小さくなる山を探しましょう。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
方針 通常のニムでは、各山の個数のニム和（2 進法で各桁ごとに排他的論理和をとったもの）が の局面が後手必勝、 でない局面が先手必勝である。先手はニム和が の局面を相手に渡せばよい。
手順 1：2 進法で表す
手順 2：ニム和を計算する
各桁ごとに の個数が奇数なら 、偶数なら とする。
よって であり、先手必勝である。
手順 3：ニム和を にする手を探す
ある山の個数 を に変えると、全体のニム和は になる。ただし石は減らすことしかできないので、 である山を選ぶ必要がある。
- 山 A： なので不可。
- 山 B： なので不可。
- 山 C： なので可能。
（ の最上位の桁 に をもつのは山 C だけである、と見ても同じ結論になる。）
したがって、山 C から 個取り、山 C を 個にすればよい。
確認
となり、確かにニム和が の局面を相手に渡せる。
よって答えは である。
別解
これは通常の Nim である。先手が必勝となるのは、手を打った後の石の個数の XOR（ニム和）が 0 になるときである。
現在のニム和は である。、 なので、ニム和は であり、先手必勝の局面である。
各山を に減らして残りの 2 山とのニム和を 0 にできるか調べる。
- 山 A：他の 2 山の XOR は 。 なので不可能。
- 山 B：他の 2 山の XOR は 。 なので不可能。
- 山 C：他の 2 山の XOR は 。 なので、山 C を 5 個にすればよい（5 個取り除く）。
よって必勝の最初の手は山 C から 5 個取る手の 1 通りだけであり、打った直後の個数は となる。
検算： で、ニム和は 0 になっている。