石取りゲームと必勝法

同義語：石取りゲームtake-away games and winning strategies

概要

前提知識: 不変量と単調量, n進法と記数法, 数学的帰納法と整列性

出発点：10 個の石を 1〜3 個ずつ取る

机の上に 10 個の石がある。2 人が交互に、1 個、2 個、3 個のどれかの個数の石を取る。最後の石を取った人の勝ちである。先に取る人（先手）は、どう取れば必ず勝てるだろうか。

10 個の石と 1〜3 個

先手は最初に 2 個取り、8 個を残す。その後は、相手が $x$ 個取ったら、自分は $4-x$ 個取る。$x$ は $1,2,3$ のどれかなので、$4-x$ は $3,2,1$ のどれかで、規則どおりに取れる。1 往復で石はちょうど $x+(4-x)=4$ 個減るので、相手に渡す石の数は
$$ 8\ \to\ 4\ \to\ 0 $$
と $4$ の倍数のまま減っていく。最後に $0$ 個を相手に渡したとき、最後の石を取ったのは先手なので、先手が勝つ。
たとえば相手が 3 個取れば（残り 5 個）自分は 1 個取って 4 個を渡し、相手が 1 個取れば（残り 3 個）自分は 3 個取って勝つ。
逆に、最初の石が 8 個なら、先手がどう取っても後手が同じ方法で $4$ の倍数を渡し続けられるので、後手が勝つ。

この例で使ったのは、「$4$ の倍数」という局面の集まりが、次の性質をもつことである。

$4$ の倍数の局面からどう取っても、$4$ の倍数でない局面になる。
$4$ の倍数でない局面からは、うまく取れば $4$ の倍数の局面にできる。
これは不変量と単調量で見た不変量に似ている。「相手に渡す局面が $4$ の倍数である」ことを、勝つ側が自分の手で保ち続ける。この記事では、この考え方を一般のゲームで述べ、次の問いに答える。

1 つの山から $1$〜$m$ 個取るゲームでは、どちらが勝つか。→ thm-tk-one
山がいくつもあり、1 つの山から何個でも取れるゲーム（Nim）では、どちらが勝つか。→ thm-tk-bouton

どちらの答えも、同じ判定法で示せるか。→ lem-tk-lose

高校の言葉	この記事の言葉	大学の言葉
$4$ の倍数を相手に渡す	負けの局面を渡す	後手必勝の局面（P 局面）
余りで場合を分ける	余りによる判定	周期的な判定
2 進法で書いて各けたを比べる	Nim 和	2 進法の繰り上がりのない足し算

言葉の準備：局面・手・必勝

石取りゲーム

いくつかの山に石があり、2 人が交互に手を打つ。1 回の手では、決められた規則に従って石を取る。石が減らない手はない。規則に従う手がなくなった局面を 終わりの局面 といい、終わりの局面で手番になった人が負ける（つまり、最後に手を打った人が勝つ）。
局面 $p$ で手番の人を「先手」、もう 1 人を「後手」とよぶ。局面 $p$ が 先手必勝 であるとは、先手に、後手がどう打っても必ず勝てる打ち方（必勝法）があることをいう。後手必勝 であるとは、後手に必勝法があることをいう。

石は 1 回の手で必ず減るので、石の総数は不変量と単調量の意味の単調量（$0$ 以上の整数で、手のたびに必ず減る量）であり、ゲームは最初の石の総数以下の回数で必ず終わる（同じ記事の定理「単調量の原理」）。

小さな局面

1 つの山から $1$〜$3$ 個取るゲームで考える。
(1) 石が $0$ 個の局面は終わりの局面で、手番の人が負ける。後手必勝である。
(2) 石が $1$、$2$、$3$ 個の局面は先手必勝である。先手は全部取って、$0$ 個の局面を後手に渡せばよい。
(3) 石が $4$ 個の局面は後手必勝である。先手が $x$ 個（$x=1,2,3$）取ると $4-x$ 個が残り、これは (2) の局面なので、後手は残りを全部取って勝つ。

判定法：負けの局面の集まり

ex-tk-ten の「$4$ の倍数」を一般にしたものが、次の補題である。

負けの局面の集まりによる判定

石取りゲームの局面の集まり $L$ が、次の 3 つの条件をみたすとする。
(R1) 終わりの局面はすべて $L$ に属する。
(R2) $L$ に属する局面から、どの手を打っても $L$ に属さない局面になる。
(R3) $L$ に属さない局面からは、$L$ に属する局面になる手が少なくとも 1 つある。
このとき、$L$ に属する局面は後手必勝であり、$L$ に属さない局面は先手必勝である。

$L$ の局面を相手に渡し続ける

方針：$L$ に属さない局面で手番の人が、いつも $L$ の局面を相手に渡せば勝てることを示す。
段 1（打ち方を決める）。$L$ に属さない局面 $p$ で手番の人を A、相手を B とする。A は次の打ち方をする：自分の手番の局面が $L$ に属さなければ、条件 (iii) により $L$ に属する局面になる手があるので、その手を打つ。
段 2（A はいつも $L$ に属さない局面で手番になる）。最初の局面 $p$ は $L$ に属さない。A が $L$ に属する局面を B に渡すと、B がどの手を打っても、条件 (ii) により $L$ に属さない局面になる。したがって、A の手番の局面はいつも $L$ に属さず、A は段 1 の打ち方を続けられる。
段 3（A は終わりの局面で手番にならない）。条件 (i) により、終わりの局面は $L$ に属する。段 2 により A の手番の局面は $L$ に属さないので、A の手番の局面は終わりの局面ではない。つまり A には必ず打てる手がある。
段 4（A が勝つ）。石は 1 回の手で必ず減るので、ゲームは有限回で終わる。終わるのは、手番の人が打てなくなったときである。段 3 により、それは A ではなく B である。よって A が勝ち、$p$ は先手必勝である。
段 5（$L$ に属する局面）。$L$ に属する局面 $q$ で先手が打つと、条件 (ii) により $L$ に属さない局面になる（$q$ が終わりの局面なら、先手は打てずにすぐ負ける）。その局面では後手が手番なので、段 1〜4 の A の役を後手が行えば後手が勝つ。よって $q$ は後手必勝である。$\square$

条件 (i) は条件 (iii) から出てくる。終わりの局面には打てる手がないので、それが $L$ に属さなければ条件 (iii) に反するからである。それでも (i) を書いておくと、$L$ を探すときの出発点（「終わりの局面は負け」）が見えやすい。
負けの局面の集まりをこの 3 つの性質で特徴づける考え方は、BTB11 の第 3 章（§3.2、pp. 130–131）で、負けの局面を balanced、勝ちの局面を unbalanced とよんで説明されている。1 つの山から決まった個数を取るゲームは同じ本の §3.2.7（pp. 135–136）の問題にある。補題の 3 つの条件は、不変量と単調量の考え方の組み合わせである。条件 (ii) と (iii) は「勝つ側が保ち続ける性質」を、手の数が有限であることは「石の数という単調量」を表している。

主定理 1：1 つの山から $1$〜$m$ 個取るゲーム

1 つの山のゲーム

$m$ を正の整数とする。1 つの山から、1 回に $1$ 個以上 $m$ 個以下の石を取るゲームで、石が $n$ 個の局面は、$n$ が $m+1$ の倍数なら後手必勝、$m+1$ の倍数でなければ先手必勝である。先手必勝のとき、先手は $n$ を $m+1$ で割った余りの個数だけ取ればよい。

3 つの条件を確かめる

方針：$L$ を「石の数が $m+1$ の倍数である局面」の集まりとし、lem-tk-lose の 3 つの条件を確かめる。
段 1（条件 (i)）。終わりの局面は石が $0$ 個の局面だけである（石が $1$ 個以上あれば $1$ 個取る手がある）。$0=(m+1)\cdot0$ は $m+1$ の倍数なので、$L$ に属する。
段 2（条件 (ii)）。石が $n=(m+1)q$ 個（$q\ge1$）の局面から $x$ 個（$1\le x\le m$）取ると、残りは
$$ (m+1)q-x=(m+1)(q-1)+(m+1-x) $$
個である。$1\le x\le m$ より $1\le m+1-x\le m$ なので、残りを $m+1$ で割った余りは $m+1-x$ で、$0$ でない。よって残りは $m+1$ の倍数でなく、$L$ に属さない。
段 3（条件 (iii)）。石の数 $n$ が $m+1$ の倍数でないとき、$n=(m+1)q+j$（$q\ge0$、$1\le j\le m$）と割り算できる。$1\le j\le m$ かつ $j\le n$ なので、$j$ 個取る手は規則どおりで、残りは $(m+1)q$ 個で $L$ に属する。
段 1〜3 と lem-tk-lose から結論が従う。先手の取る個数は段 3 の $j$ である。$\square$

石の数 0 から 15 の局面を、1〜3 個取るゲームの勝ち負けで色分けした。4 の倍数（赤の数字）が負けの局面で、10 個からは 2 個取って 8 個にする
図 1 は $m=3$ の場合である。負けの局面は $0,4,8,12$ で、4 個ごとに現れる。ex-tk-ten では $10=4\cdot2+2$ なので、先手は 2 個取る。

ほかの $m$ で

$m=2$（1 個か 2 個取る）で石が 7 個なら、$7=3\cdot2+1$ なので先手必勝で、先手は 1 個取って 6 個を渡す。負けの局面は $0,3,6,9,\dots$ である。
$m=4$（1〜4 個取る）で石が 20 個なら、$20=5\cdot4$ なので後手必勝である。先手が $x$ 個取ったら、後手は $5-x$ 個取ればよい。
$m=1$（1 個ずつしか取れない）なら、負けの局面は偶数個の局面である。このゲームでは打ち方に選ぶ余地がなく、石が奇数個なら先手が最後の石を取る。定理は、選ぶ余地のない場合も含んでいる。

Nim 和：2 進法で繰り上がりなしに足す

山が 1 つ以上あり、1 回の手で 1 つの山を選んで、その山から 1 個以上何個でも 取れるゲームを Nim という。山の石の数が $a_1,a_2,\dots,a_k$ の局面を $(a_1,a_2,\dots,a_k)$ と書く（BTB11 の §3.4、p. 144）。
山が 2 つなら答えは簡単である。$(a,a)$ のように 2 つの山が同じ数なら後手必勝で、後手は先手がある山から取ったのと同じ数を、もう一方の山から取ればよい（まねをする打ち方）。図 2 は、2 つの山の局面 $(a,b)$ を平面の点で表し、負けの局面 $a=b$ に色を付けたものである。山が 3 つ以上になると、まねをする打ち方は使えない。そこで次の計算を使う。
2 つの山の Nim の局面を点で表すと、負けの局面は 2 つの山の石の数が等しい対角線の上にある。矢印は、1 つの山から取って対角線の上に移る手である

Nim 和

$0$ 以上の整数 $a_1,a_2,\dots,a_k$ を 2 進法で書き（n進法と記数法）、各けたごとに $1$ の個数を数える。その個数が奇数のけたを $1$、偶数のけたを $0$ とする 2 進法の数を、$a_1,\dots,a_k$ の Nim 和 といい、$a_1\oplus a_2\oplus\cdots\oplus a_k$ と書く。

各けたで「足して $2$ で割った余り」をとり、繰り上がりをしない足し算である。Nim 和の計算は BTB11 の §3.10.3（p. 175）に、Nim 和が $0$ の局面が負けの局面であることは §3.10.7（p. 180）にある。

Nim 和の計算

$3,5,7$ の Nim 和。2 進法で $3=011$、$5=101$、$7=111$（けたは左から $4$ の位・$2$ の位・$1$ の位）。下の表のように、$4$ の位の $1$ は 2 個、$2$ の位の $1$ は 2 個、$1$ の位の $1$ は 3 個なので、Nim 和は $001$、つまり
$$ 3\oplus5\oplus7=1 $$
である。普通の和 $3+5+7=15$ とは違う。
$1,2,3$ の Nim 和。$1=01$、$2=10$、$3=11$ で、どのけたも $1$ が 2 個なので $1\oplus2\oplus3=0$ である。
$4,7,9$ の Nim 和。$4=0100$、$7=0111$、$9=1001$ で、$8$ の位の $1$ は 1 個、$4$ の位は 2 個、$2$ の位は 1 個、$1$ の位は 2 個なので、Nim 和は $1010$、つまり $4\oplus7\oplus9=10$ である。

	$8$ の位	$4$ の位	$2$ の位	$1$ の位
$3$	$0$	$0$	$1$	$1$
$5$	$0$	$1$	$0$	$1$
$7$	$0$	$1$	$1$	$1$
$1$ の個数	$0$	$2$	$2$	$3$
$3\oplus5\oplus7$	$0$	$0$	$0$	$1$

主定理 2：Nim 和が $0$ なら後手必勝

Nim の必勝法（Bouton の定理）

Nim の局面 $(a_1,a_2,\dots,a_k)$ は、Nim 和 $a_1\oplus a_2\oplus\cdots\oplus a_k$ が $0$ なら後手必勝、$0$ でなければ先手必勝である。

証明では、2 進法の数の大小について次の事実を使う。

2 進法の数の大小

2 つの $0$ 以上の整数 $a,b$ を 2 進法で書き、上のけたから比べて、初めて違うけたが $2^d$ の位で、そのけたが $a$ では $1$、$b$ では $0$ とする。このとき $a>b$ である。

下のけたの和で押さえる

$2^d$ の位より上のけたは $a$ と $b$ で同じなので、その部分の値を $c$ とする。$b$ の $2^d$ の位は $0$ で、それより下のけたは多くても全部 $1$ なので、$b\le c+(2^{d-1}+\cdots+2+1)=c+2^d-1$ である（等比数列の和）。一方 $a\ge c+2^d$ である。よって $a-b\ge1$ である。$\square$

負けの局面を Nim 和が $0$ の局面とする

方針：$L$ を「Nim 和が $0$ の局面」の集まりとし、lem-tk-lose の 3 つの条件を確かめる。
段 1（条件 (i)）。終わりの局面は、すべての山が $0$ 個の局面 $(0,0,\dots,0)$ だけである。どのけたにも $1$ がないので、Nim 和は $0$ で、$L$ に属する。
段 2（条件 (ii)）。Nim 和が $0$ の局面で、ある山の石の数を $a$ から $a'$（$a'< a$）に変える。$a\ne a'$ なので、2 進法で書いたとき $a$ と $a'$ で違うけたが少なくとも 1 つある。そのけたでは、ほかの山の数字は変わらず、この山の数字だけが $0$ と $1$ で入れかわるので、$1$ の個数はちょうど $1$ だけ増えるか減る。変える前は Nim 和が $0$ で、そのけたの $1$ の個数は偶数だったので、変えた後は奇数になる。よって変えた後の Nim 和のそのけたは $1$ で、Nim 和は $0$ でない。
段 3（条件 (iii)）。Nim 和 $s=a_1\oplus\cdots\oplus a_k$ が $0$ でない局面を考える。$s$ の 2 進法で $1$ になっている最も上のけたを $2^d$ の位とする。$s$ のそのけたが $1$ なので、そのけたで $1$ をもつ山の数は奇数個で、とくに $1$ 個以上ある。そのような山を 1 つ選び、石の数を $a$ とする。
$a$ の 2 進法の数字のうち、$s$ で $1$ になっているけたの数字をすべて入れかえた（$0$ を $1$ に、$1$ を $0$ にした）数を $a'$ とする。$s$ の $2^d$ の位より上のけたはすべて $0$ なので、$a$ と $a'$ はそれより上のけたで同じであり、$2^d$ の位は $a$ で $1$、$a'$ で $0$ である。lem-tk-compare により $a'< a$ なので、この山から $a-a'$ 個取って $a'$ 個にする手は規則どおりである。
この手の後の Nim 和を調べる。$s$ で $1$ だったけたでは、この山の数字が入れかわるので、$1$ の個数が $1$ だけ変わり、奇数から偶数になる。$s$ で $0$ だったけたでは何も変わらず、$1$ の個数は偶数のままである。よってどのけたも $1$ の個数が偶数になり、Nim 和は $0$ で、$L$ に属する。
段 1〜3 と lem-tk-lose から結論が従う。$\square$

段 3 の $a'$ は、各けたで「$a$ の数字と $s$ の数字の Nim 和」をとった数、つまり $a'=a\oplus s$ である。

勝つ手を求める

局面 $(3,5,7)$ では ex-tk-nimsum (1) より Nim 和は $s=1$ で、先手必勝である。$s$ の $1$ は $1$ の位だけなので、$1$ の位が $1$ の山を選ぶ。$3,5,7$ はどれも $1$ の位が $1$ である。$3$ の山を選ぶと $a'=3\oplus1=2$ で、1 個取って $(2,5,7)$ にする。確かめると $2=010$、$5=101$、$7=111$ で、どのけたも $1$ が 2 個なので $2\oplus5\oplus7=0$ である。$5$ の山から 1 個取って $(3,4,7)$、$7$ の山から 1 個取って $(3,5,6)$ にしてもよい。
局面 $(1,2,3)$ は Nim 和が $0$ なので後手必勝である。たとえば先手が $3$ の山を全部取って $(1,2,0)$ にすると、Nim 和は $1\oplus2=3$ で、後手は $2$ の山から 1 個取って $(1,1,0)$ にすれば Nim 和 $0$ を渡せる。
局面 $(4,7,9)$ は Nim 和が $s=10$（2 進法で $1010$）である。$s$ の $1$ の最も上のけたは $8$ の位で、そのけたが $1$ の山は $9=1001$ だけである。$a'=9\oplus10$ は、$9$ の $8$ の位と $2$ の位の数字を入れかえた $0011=3$ なので、$9$ の山から 6 個取って $(4,7,3)$ にする。$4=100$、$7=111$、$3=011$ で Nim 和は $0$ である。この局面で Nim 和を $0$ にする手は、この 1 つだけである。

で $8$ の位に $1$ をもつ山を選んだのは、prf-tk-bouton の段 3 のとおりである。$7$ の山を選んで $7\oplus10=13$ にしようとしても、$13>7$ なので石を増やすことになり、手として打てない。

例と反例

規則を少し変えると、判定がどう変わるかを並べる。

変える規則	反例	成り立たなくなること
最後の石を取った人が勝ち	最後の石を取った人が負け、局面 $(1)$ と $(1,1)$	Nim 和が $0$ なら後手必勝
取れる数が $1$ から $m$ まで全部	取れる数が $1,3,4$ だけ	負けの局面が $m+1$ の倍数

反例：最後の石を取った人が負けの Nim

規則を「最後の石を取った人が負け」に変える。
(1) 局面 $(1)$（山が 1 つで石が 1 個）では、先手は 1 個取るしかなく、最後の石を取って負ける。Nim 和は $1\ne0$ なのに後手必勝である。
(2) 局面 $(1,1)$ では、先手が 1 個取ると後手は最後の石を取るしかなく、先手が勝つ。Nim 和は $1\oplus1=0$ なのに先手必勝である。
このように thm-tk-bouton の判定は成り立たない。この規則では、def-tk-game の「終わりの局面で手番になった人が負ける」が「勝つ」に変わる。lem-tk-lose の証明の段 4 はこの規則を使っているので、補題がそのままでは使えなくなるからである。この規則の Nim でも、1 か所を直すだけで判定ができることが知られており、Nim で扱う。

反例：取れる数が $1,3,4$ のゲーム

1 つの山から、1 回に $1$ 個、$3$ 個、$4$ 個のどれかを取るゲームを考える（$2$ 個は取れない）。小さい局面から順に調べると、負けの局面は
$$ 0,\ 2,\ 7,\ 9,\ 14,\ 16,\ 21,\ 23,\ \dots $$
で、「$7$ で割った余りが $0$ か $2$」の局面である（図 3）。thm-tk-one のような「ある数の倍数」の形ではない。
lem-tk-lose で確かめる。$L$ を $7$ で割った余りが $0$ か $2$ の局面の集まりとする。
条件 (i)：終わりの局面は $0$ 個だけで、$L$ に属する。
条件 (ii)：余り $0$ の局面から $1,3,4$ 個取ると余りは $6,4,3$ になり、余り $2$ の局面から取ると余りは $1,6,5$ になる（取れる場合だけ）。どれも $0$ でも $2$ でもない。
条件 (iii)：余りが $1$ なら $1$ 個取って余り $0$ に、余りが $3$ なら $3$ 個取って余り $0$ に、余りが $4$ なら $4$ 個取って余り $0$ に、余りが $5$ なら $3$ 個取って余り $2$ に、余りが $6$ なら $4$ 個取って余り $2$ にできる。どの場合も石は取る個数以上ある（余りが $r$ なら石は $r$ 個以上ある）。
よって負けの局面はちょうど $L$ である。

取れる数が 1、3、4 のゲームで、石の数 0 から 20 の局面を色分けした。負けの局面は 7 で割った余りが 0 か 2 の局面で、7 個ごとに同じ並びが続く

大学数学で見る：Grundy 数とゲームの和

Nim の局面 $(a_1,\dots,a_k)$ は、1 つの山だけのゲームを $k$ 個並べ、手番の人がそのうち 1 つを選んで 1 手打つゲームと見られる。このような並べ方を ゲームの和 という。thm-tk-bouton は、1 つの山のゲームの「強さ」を山の石の数で表し、和のゲームの勝ち負けがそれらの Nim 和で決まることを述べている。

Sprague–Grundy の定理へ

石取りゲームに限らず、2 人に許される手が同じで（打てる手が局面だけで決まり、手番の人によらない）、各局面から打てる手が有限個で、有限回で必ず終わり、最後に手を打った人が勝つ 2 人のゲーム（不偏ゲーム）では、各局面に Grundy 数 とよばれる $0$ 以上の整数を対応させることができ、ゲームの和の Grundy 数は各ゲームの Grundy 数の Nim 和になる。Grundy 数が $0$ の局面がちょうど後手必勝の局面である。これを Sprague–Grundy の定理といい、Nim で扱う。この記事では証明しない。ex-tk-cx-134 のゲームの山をいくつも並べたゲームも、この定理で判定できる。

Nim 和は、2 進法の各けたを「$2$ で割った余り」で足す計算である。$0$ と $1$ だけの世界で $1+1=0$ とする足し算を、各けたで行っていることになる（合同式の計算規則の法 $2$ の計算）。

さらに先へ

Nim では、同じ Bouton の定理を大学の言葉で述べ、最後の石を取った人が負けの規則と、Sprague–Grundy の定理を扱う。
次に読む Ramsey数 R(3,3)=6 では、6 個の点のどの 2 点も線で結び、線を 2 色に塗るとき、どう塗っても同じ色の三角形が必ず現れることを示す。「相手がどう打っても」勝てることを示したこの記事と同じく、「どう塗っても」成り立つことを場合を尽くさずに示す議論である。
この記事の lem-tk-lose は、前の記事塗り分けによる証明と不変量と単調量の考え方（保たれる性質と、必ず減る量）を 2 人のゲームに使ったものである。
$m+1$ で割った余りによる判定は合同式の計算規則、2 進法の書き方は n進法と記数法で扱う。