§C5.4彩色論法

敷き詰めることはできない。

盤を市松模様に塗る。各行には8マスが黒と白の交互に並ぶので、各行の黒マスと白マスはそれぞれ4個であり、盤全体の黒マスと白マスはそれぞれ32個である。同色の2マスを取り除くと、取り除いた色のマスは30個、他方の色のマスは32個になる。

上下または左右に隣り合う2マスは異なる色であるから、ドミノ1枚は黒マス1個と白マス1個を覆う。敷き詰めることができたとし、用いたドミノの枚数を$k$とすると、覆われた黒マスと白マスはともに$k$個であり、残りの盤の黒マスと白マスの個数は等しくなければならない。この結論は、二つの色のマスの個数が30個と32個であることに反する。したがって、敷き詰めることはできない。▨

$i$行$j$列のマスを$(i,j)$と書く（$i=1,2$、$j=1,\ldots,n$）。$i+j$が偶数のマスを黒、奇数のマスを白に塗る。上下または左右に隣り合う2マスは、$i$と$j$の一方だけが$1$異なるので、異なる色である。したがって、ドミノ1枚は黒マス1個と白マス1個を覆う。各列には黒マスと白マスが1個ずつあるので、盤全体の黒マスと白マスはそれぞれ$n$個である。

四隅は$(1,1),(2,1),(1,n),(2,n)$であり、$n\ge2$からこの四つは相異なる。2マスの選び方を三つの場合に分ける。

同じ列の2マス$(1,1),(2,1)$を取り除く場合、残りの盤は$2\times(n-1)$盤であり、各列を縦向きのドミノ1枚で覆うと敷き詰めることができる。$(1,n),(2,n)$を取り除く場合も同じである。

同じ行の2マス$(1,1),(1,n)$を取り除く場合、二つのマスの$i+j$は$2$と$n+1$である。$n$が奇数なら二つのマスは同じ色であり、残りの盤の黒マスと白マスの個数は$n-2$個と$n$個になって異なるので、敷き詰めることはできない。$n$が偶数なら、2行目のマスを$(2,2k-1),(2,2k)$（$k=1,\ldots,n/2$）の組に分け、1行目に残る$(1,2),\ldots,(1,n-1)$を$(1,2k),(1,2k+1)$（$k=1,\ldots,(n-2)/2$）の組に分ける。各組は左右に隣り合う2マスであるから、横向きのドミノで敷き詰めることができる。$(2,1),(2,n)$を取り除く場合は、1行目と2行目の役割を入れ替えて同じ結論を得る。

対角の位置にある2マス$(1,1),(2,n)$を取り除く場合、二つのマスの$i+j$は$2$と$n+2$である。$n$が偶数なら二つのマスは同じ色であり、同じ行の2マスを取り除く場合と同じ理由で、敷き詰めることはできない。$n$が奇数なら、1行目に残る$(1,2),\ldots,(1,n)$を$(1,2k),(1,2k+1)$（$k=1,\ldots,(n-1)/2$）の組に分け、2行目に残る$(2,1),\ldots,(2,n-1)$を$(2,2k-1),(2,2k)$（$k=1,\ldots,(n-1)/2$）の組に分けると、横向きのドミノで敷き詰めることができる。$(2,1),(1,n)$を取り除く場合も、行の役割を入れ替えて同じ結論を得る。

以上より、敷き詰めることができないのは、同じ行の両端の2マスを取り除き$n$が奇数である場合と、対角の位置にある2マスを取り除き$n$が偶数である場合であり、いずれも取り除く2マスが同じ色になる場合である。それ以外の場合には敷き詰めることができる。▨

奇閉路の頂点を閉路に沿って$v_0,v_1,\ldots,v_{k-1}$とし、辺を$v_0v_1,v_1v_2,\ldots,v_{k-2}v_{k-1},v_{k-1}v_0$とする。$k$は$3$以上の奇数である。辺の両端が異なる色になるように2色で塗ることができたと仮定する。

$0\le i\le k-1$を満たす整数$i$について、「$v_i$が$v_0$と同じ色であることは、$i$が偶数であることと同値である」を$i$についての数学的帰納法で示す。$i=0$のときは成り立つ。$i$で成り立つとすると、$v_{i+1}$は$v_i$と辺で結ばれているので$v_i$と異なる色であり、色は2色しかないので、$v_{i+1}$の色は$v_i$の色でない方の色である。したがって、$v_{i+1}$が$v_0$と同じ色であることは、$v_i$が$v_0$と異なる色であること、すなわち$i$が奇数であることと同値であり、$i+1$が偶数であることと同値である。

$k$は奇数であるから$k-1$は偶数であり、$v_{k-1}$は$v_0$と同じ色である。ところが$v_{k-1}$と$v_0$は辺で結ばれているので、異なる色でなければならない。この矛盾により、奇閉路の頂点をそのように2色で塗ることはできない。▨

一例を挙げる。座標平面の格子点$(x,y)$（$x,y$は整数）にある駒を、一回の操作で

のいずれかへ動かす。駒は原点$(0,0)$から出発する。

三つの移動による$x+y$の変化は、それぞれ$3$、$0$、$-3$であり、いずれも$3$の倍数である。そこで、格子点$(x,y)$を、$x+y$を$3$で割った余りによって3色に塗る。一回の操作で駒の位置の色は変わらない。したがって、操作の回数についての数学的帰納法により、原点から到達することができるすべての格子点で、$x+y$は$3$の倍数である。

点$(1,0)$では$x+y=1$であり、$3$の倍数でない。よって、駒は点$(1,0)$に到達することができない。▨