ニムとニム和

石の個数を 2 進法で表し、排他的論理和（ニム和） $a_{1} \oplus a_{2} \oplus \dots \oplus a_{k}$ を計算できる。ニム和が $0$ かどうかで先手必勝・後手必勝を判定し、ニム和を $0$ にする手を求められる

前提

n 進法（数学A 整数の性質）

この技能までの道筋（7 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
n 進法（数学A 整数の性質）

説明

ニムは、いくつかの山に分かれた石を 2 人が交互に取り合うゲームです。1 回の手番では 1 つの山を選び、その山から 1 個以上の石を取ります（全部取ってもかまいません）。最後の石を取った人が勝ちです。各山の石の個数を 2 進法で表して「ニム和」を計算すると、局面を見ただけで先手と後手のどちらが必勝かが判定できます。さらに、勝つためにどの山から何個取ればよいかも求められます。

なぜそうしてよいのか

0 以上の整数 $a, b$ のニム和 $a \oplus b$ は、次の手順で作る数です。 $a, b$ を 2 進法で表して桁をそろえ、各桁ごとに「 $0 \oplus 0 = 0, 0 \oplus 1 = 1 \oplus 0 = 1, 1 \oplus 1 = 0$ 」と計算します。これは、繰り上がりのない足し算を 2 で割った余りで行うことにあたります。たとえば $3 = 01 1_{(2)}$ 、 $5 = 10 1_{(2)}$ なので $3 \oplus 5 = 11 0_{(2)} = 6$ です。この演算は順序を入れ替えても組み方を変えても結果が同じなので、 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{k}$ が意味をもちます。各桁を見ると、その桁に 1 をもつ山の数が奇数なら 1、偶数なら 0 になります。また $a \oplus a = 0$ 、 $a \oplus 0 = a$ が成り立ちます。

ニム和 $s = a_{1} \oplus \dots \oplus a_{k}$ について、次の 2 つの事実が成り立ちます。(1) $s = 0$ の局面からどう動かしても、 $s \neq = 0$ になる。1 つの山を $a_{i}$ から $a_{i}^{'} (\neq = a_{i})$ に変えると、新しいニム和は $s \oplus a_{i} \oplus a_{i}^{'} = a_{i} \oplus a_{i}^{'}$ です。 $a_{i} \neq = a_{i}^{'}$ なのでどこかの桁が食い違い、この値は 0 になりません。(2) $s \neq = 0$ の局面からは、 $s = 0$ にする手が必ずある。 $s$ の 2 進法で 1 が立っている最上位の桁を $2^{m}$ の位とします。 $s$ のこの桁が 1 なので、この桁が 1 である山 $a_{i}$ が少なくとも 1 つあります。 $a_{i}$ を $a_{i} \oplus s$ に変えると、 $2^{m}$ の位より上の桁は変わらず、 $2^{m}$ の位は 1 から 0 になります。それより下の桁がどう変わっても、下の桁の値の合計は最大でも $2^{m} - 1 < 2^{m}$ です。よって $a_{i} \oplus s < a_{i}$ となり、石を取る正しい手になります。このときの新しいニム和は $s \oplus a_{i} \oplus (a_{i} \oplus s) = 0$ です。

石が全部なくなった局面のニム和は 0 です。そこで $s \neq = 0$ の局面で手番の人が毎回 (2) の手を打つと、相手には (1) により必ず $s \neq = 0$ の局面を返されます。石は毎手減るのでゲームは必ず終わり、最後の石を取るのは $s \neq = 0$ の局面で手番を迎える側です。したがって、ニム和が $0$ でなければ手番の人（先手）の必勝、 $0$ なら後手の必勝です。

手順

各山の石の個数を 2 進法で表し、桁をそろえて縦に並べる
各桁ごとに 1 の個数を数え、奇数なら 1、偶数なら 0 としてニム和 $s = a_{1} \oplus \dots \oplus a_{k}$ を求める
判定する: $s = 0$ なら後手必勝、 $s \neq = 0$ なら先手必勝
$s \neq = 0$ のときは、 $s$ の最上位の 1 の桁を見つけ、その桁が 1 である山 $a_{i}$ を選ぶ
選んだ山を $a_{i} \oplus s$ 個にする（取る個数は $a_{i} - (a_{i} \oplus s)$ ）。これで全体のニム和が $0$ になる

例題

石の山が 3 つあり、山 A に 6 個、山 B に 9 個、山 C に 13 個の石がある。ニムを行うとき（1 つの山から 1 個以上取る。最後の石を取った人が勝ち）、先手がニム和を $0$ にする手を打つ。そのような手はただ 1 つである。手を打った後の山 A, B, C の石の個数を、順に組 $(A, B, C)$ で求めよ。

例題の解答

手順 1: $6 = 011 0_{(2)}$ 、 $9 = 100 1_{(2)}$ 、 $13 = 110 1_{(2)}$ と表し、桁をそろえる。
手順 2: 各桁の 1 の個数を数える。 $8$ の位は $0, 1, 1$ で 2 個なので 0。 $4$ の位は $1, 0, 1$ で 2 個なので 0。 $2$ の位は $1, 0, 0$ で 1 個なので 1。 $1$ の位は $0, 1, 1$ で 2 個なので 0。よって $s = 001 0_{(2)} = 2$ である。
手順 3: $s \neq = 0$ なので先手必勝である。
手順 4: $s$ の最上位の 1 は $2$ の位にある。 $2$ の位が 1 である山は A（ $011 0_{(2)}$ ）だけである。実際、B では $9 \oplus 2 = 11 > 9$ 、C では $13 \oplus 2 = 15 > 13$ となり、どちらも石を増やすことになるので手にならない。
手順 5: 山 A を $6 \oplus 2 = 011 0_{(2)} \oplus 001 0_{(2)} = 010 0_{(2)} = 4$ 個にする（2 個取る）。確認すると $4 \oplus 9 \oplus 13 = 0100 \oplus 1001 \oplus 1101 = 000 0_{(2)} = 0$ となる。
よって、手を打った後は $(4, 9, 13)$ である。

答え: $(4, 9, 13)$

よくある誤り

普通の足し算のように繰り上げてしまう誤り。たとえば $3 \oplus 5$ を $011 + 101 = 100 0_{(2)} = 8$ とするのは誤り。正しくは各桁を繰り上がりなしで計算し、 $3 \oplus 5 = 11 0_{(2)} = 6$ である。
ニム和が $0$ のときに先手必勝と判定してしまう誤り。正しくは、 $s = 0$ なら手番の人がどう動いても $s \neq = 0$ になるので、後手必勝である。先手必勝になるのは $s \neq = 0$ のときである。
取る個数をニム和 $s$ そのものにしてしまう誤り。たとえば山が $1, 2$ のとき $s = 1 \oplus 2 = 3$ だが、3 個は取れない。正しくは、山 $2$ を $2 \oplus 3 = 1$ 個にする。つまり取る個数は $a_{i} - (a_{i} \oplus s) = 2 - 1 = 1$ 個である。
$s$ の最上位の桁が 0 である山を選んでしまう誤り。その山では $a_{i} \oplus s > a_{i}$ となり、石を増やす必要が出てくる（例: 山 $9$ に $s = 2$ なら $9 \oplus 2 = 11 > 9$ ）。正しくは、 $s$ の最上位の 1 の桁が 1 である山を選ぶ。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

山を分けるゲームのグランディ数（大学数学ゲーム理論）
スプレイグ・グランディの定理と勝ちにつながる手（大学数学ゲーム理論）