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