§C5.2不変量と単調量

$i$行$j$列のマスを$(i,j)$と書き、$i+j$が偶数のマスを黒、奇数のマスを白に塗る。上下または左右に隣り合う2マスは異なる色である。取り除く2マスが異なる色であるとき、かつそのときに限り、残りの盤を敷き詰めることができることを示す。

取り除く2マスが同じ色である場合は、本文の市松模様の議論と同じく、敷き詰めることはできない。元の盤の黒マスと白マスは32個ずつであるから、残りの盤では一方の色が30個、他方の色が32個になり、黒マス1個と白マス1個を覆うドミノでは覆うことができない。

取り除く2マスが異なる色である場合に敷き詰めることができることを示す。64個のマスを一周する次の順路を考える。1行目を$(1,1)$から$(1,8)$まで右へ進み、2行目を$(2,8)$から$(2,2)$まで左へ、3行目を$(3,2)$から$(3,8)$まで右へ進む。以下同様に、2行目から8行目までは2列目から8列目までを行ごとに向きを変えて進み、偶数行では左へ、奇数行では右へ進む。8行目は$(8,2)$で終わるので、続けて$(8,1)$へ進み、1列目を$(7,1),(6,1),\ldots,(2,1)$と上へ進んで$(1,1)$に戻る。この順路は、1行目の8マス、2行目から8行目までの2列目から8列目の49マス、1列目の2行目から8行目の7マスを、それぞれちょうど一度ずつ通る。$8+49+7=64$であるから、すべてのマスをちょうど一度ずつ通る。また、順路で続く2マスは上下または左右に隣り合い、最後のマス$(2,1)$と最初のマス$(1,1)$も隣り合う。

順路に沿ってマスを$c_0=(1,1),c_1,\ldots,c_{63}=(2,1)$と番号付ける。続く2マスは異なる色であるから、$c_t$が$c_0$と同じ色であることは$t$が偶数であることと同値である。取り除く2マスを$c_p,c_q$（$0\le p<q\le63$）とすると、二つは異なる色であるから$q-p$は奇数である。残りの62マスは、次の二つの列に分かれる。

一つ目の列のマスの個数は$q-p-1$で偶数であり（$0$個のこともある）、二つ目の列のマスの個数は$64-(q-p)-1=63-(q-p)$で偶数である。どちらの列でも、続く2マスは隣り合う（二つ目の列では$c_{63}$と$c_0$も隣り合う）。各列を先頭から2マスずつの組に分けると、各組は隣り合う2マスであり、ドミノ1枚で覆うことができる。したがって、残りの盤を敷き詰めることができる。

以上より、取り除く2マスの位置は、二つのマスの$i+j$の偶奇が異なる（異なる色である）場合が敷き詰めることができる場合、偶奇が等しい（同じ色である）場合が敷き詰めることができない場合に分類される。▨

1回の操作では、選んだ2数の偶奇がともに入れ替わり、残りの1数の偶奇は変わらない。3数のうち奇数であるものの個数を$k$とすると、選んだ2数がともに奇数なら$k$は$2$減り、ともに偶数なら$2$増え、一方が奇数で他方が偶数なら変わらない。したがって、$k$の偶奇は操作によって変わらない。3数の和は1回の操作で$2$増えるので、$k$の偶奇は3数の和の偶奇と言い換えることもできる。たとえば、偶奇の組が（偶, 偶, 奇）である3数からは、3数がすべて偶数である状態に到達することはできない。

偶奇の組についての不変量は、この$k$の偶奇だけである。実際、偶奇の組のうち$k$の偶奇が等しいものは、もとの組とちょうど$0$か所または$2$か所で偶奇が異なる組である。$2$か所で異なる組へは、その2か所の数を選ぶ1回の操作で移ることができる。したがって、$k$の偶奇が等しい4通りの偶奇の組はすべて互いに到達することができ、これらを区別する不変量は存在しない。▨

ある時点の組を$(x,y)$とし、$x\ne y$とする。二数の役割は対称であるから$x>y$としてよい。操作の後の組は$(x-y,y)$である。$x,y$は整数で$x>y$であるから$x-y\ge1$であり、操作の後の組も正整数からなる。また$y\ge1$から$x-y<x$であり、$y<x$であるから、操作の後の組の最大値$\max(x-y,y)$は、操作の前の最大値$x$より小さい。

最初の組の最大値を$M_0$とし、$t$回の操作の後の組の最大値を$M_t$とする。各$M_t$は正整数であり、上に示したことから$M_{t+1}<M_t$である。どちらも整数であるから$M_{t+1}\le M_t-1$であり、$t$についての数学的帰納法により$M_t\le M_0-t$が成り立つ。$M_t\ge1$であるから、$t$回の操作を行うことができたなら$1\le M_0-t$、すなわち$t\le M_0-1$である。したがって、操作は高々$M_0-1$回で停止する。操作が停止するのは二数が等しくなったときであるから、停止したときの組は、ある正整数$g$を用いて$(g,g)$と書くことができる。

次に、最大公約数が変わらないことを示す。$x>y$とし、$d$を正の整数とする。$d$が$x$と$y$をともに割り切るならば、$x=dp$、$y=dq$（$p,q$は整数）と書くことができ、$x-y=d(p-q)$であるから、$d$は$x-y$と$y$をともに割り切る。逆に、$d$が$x-y$と$y$をともに割り切るならば、$x=(x-y)+y$であるから、同様に$d$は$x$と$y$をともに割り切る。よって、$(x,y)$の正の公約数の全体と$(x-y,y)$の正の公約数の全体は一致し、その最大のものである最大公約数も一致する。操作の回数についての数学的帰納法により、どの時点の組の最大公約数も、最初の組$(a,b)$の最大公約数に等しい。

停止したときの組$(g,g)$の最大公約数は$g$である。したがって、$a$と$b$の最大公約数を$\gcd(a,b)$と書くと$g=\gcd(a,b)$であり、停止したときの組は$\bigl(\gcd(a,b),\gcd(a,b)\bigr)$である。たとえば$(12,18)$から始めると、$(12,6)$、$(6,6)$と進んで停止し、$\gcd(12,18)=6$と一致する。▨