塗り分けによる証明

1. 縦 2 マス・横 3 マスの盤は、縦に置いたドミノ 3 枚で覆える。6 マスを 2 マスずつ覆うので、ドミノは 3 枚である。
2. 縦 3 マス・横 3 マスの盤は覆えない。ドミノ 1 枚は 2 マスを覆うので、何枚使っても覆うマスの数は偶数である。盤は 9 マスで奇数なので、覆えない。
3. 縦 4 マス・横 4 マスの盤から、左上の隅と右下の隅の 2 マスを除く。残りは 14 マスで偶数なので、(2) の理由は使えない。それでも、この 14 マスはドミノ 7 枚では覆えない。理由を、盤を市松模様に塗って見る。左上の隅を灰色として、灰色と白を交互に塗ると、右下の隅も灰色になる（左上から右へ 3 マス、下へ 3 マス進むと、色は $3+3=6$ 回変わり、$6$ は偶数だから）。$4\times4$ の盤には灰色と白が 8 マスずつあるので、2 隅を除いた盤には灰色が 6 マス、白が 8 マス残る。ドミノ 1 枚は、横に置いても縦に置いても、隣り合う 2 マス、つまり灰色 1 マスと白 1 マスを覆う。7 枚で覆えるなら、灰色も白も 7 マスずつのはずだが、実際は 6 マスと 8 マスなので覆えない。

1. ドミノと市松模様では、def-col-coloring の後に見たとおり、ドミノは余り $0$ と余り $1$ のマスを 1 つずつ覆う。$2\times3$ の盤は余り $0$ と余り $1$ が 3 マスずつで、補題の必要条件をみたす。実際にドミノ 3 枚で敷き詰められる。
2. $3\times3$ の盤では、$r+c$ が偶数のマスは $(1,1),(1,3),(2,2),(3,1),(3,3)$ の 5 マス、奇数のマスは 4 マスで、個数が違う。補題により、ドミノで敷き詰められない。ex-col-start (2) の「9 は奇数」という理由とは別の理由である。

$6\times6$ の盤から $(1,1)$ と $(6,6)$ を除いた 34 マスの盤も、ドミノ 17 枚で敷き詰められない。$6\times6$ の盤では、各行の $r+c$ が連続する 6 個の整数なので偶数と奇数が 3 個ずつで、盤全体では余り $0$ と余り $1$ が 18 個ずつある。$(1,1)$ と $(6,6)$ はどちらも $r+c$ が偶数なので、残りは余り $0$ が 16 個、余り $1$ が 18 個で、個数が違う。一般に、$m$ と $n$ が偶数の $m\times n$ の盤から向かい合う 2 隅 $(1,1)$ と $(m,n)$ を除くと、$1+1$ と $m+n$ はどちらも偶数なので、同じ議論で敷き詰められない。

$8\times8$ の盤から、同じ行の両端 $(1,1)$ と $(1,8)$ を除く。$1+1=2$ は偶数、$1+8=9$ は奇数なので、除いた 2 マスは色が違い、残りは余り $0$ と余り $1$ が 31 個ずつで、lem-col-count の必要条件をみたす。実際に敷き詰められる。1 行目の残り $(1,2)$〜$(1,7)$ の 6 マスに横のドミノを 3 枚、2 行目から 8 行目の各行に横のドミノを 4 枚ずつ置けば、ドミノは $3+4\cdot7=31$ 枚で、盤が覆われる。

$8\times8$ の盤では、各行の $r+c$ が連続する 8 個の整数なので、余り $0,1,2,3$ が 2 個ずつあり、8 行で $16$ 個ずつになる。lem-col-count の必要条件はみたされる。実際、各行に横のタイルを 2 枚ずつ置けば、16 枚で敷き詰められる（図 3）。

$6\times6$ の盤は 36 マスで、$36=4\cdot9$ なので、マスの数からは矛盾が出ない。prf-col-ten と同じ塗り方で数える。左の 4 列（$1\le c\le4$）では、各行に余り $0,1,2,3$ が 1 個ずつで、6 行で $6$ 個ずつある。右の 2 列では、5 列目の $r+c$ は $6,7,\dots,11$ で余りは $2,3,0,1,2,3$、6 列目の $r+c$ は $7,8,\dots,12$ で余りは $3,0,1,2,3,0$ である。合わせると、余り $0,1,2,3$ の個数は
$$ 6+1+2=9,\qquad 6+1+1=8,\qquad 6+2+1=9,\qquad 6+2+2=10 $$
で、そろわない。lem-col-count により、$6\times6$ の盤も $1\times4$ のタイルで敷き詰められない。

$2\times n$ の盤をドミノで敷き詰める方法の数を $a_n$ とする。$n=1$ では縦に 1 枚置くだけなので $a_1=1$、$n=2$ では縦 2 枚か横 2 枚なので $a_2=2$ である。$n=4$ の 5 通りを図 4 に示す。
$n\ge3$ のとき、左上のマス $(1,1)$ を覆うドミノで場合を分ける。
(1) $(1,1)$ が縦のドミノで覆われるとき、そのドミノは $(1,1)$ と $(2,1)$ を覆い、残りは $2\times(n-1)$ の盤である。その敷き詰め方は $a_{n-1}$ 通りある。
(2) $(1,1)$ が横のドミノで覆われるとき、そのドミノは $(1,1)$ と $(1,2)$ を覆う。このとき $(2,1)$ を覆うドミノは、上の $(1,1)$ がふさがっているので縦には置けず、$(2,1)$ と $(2,2)$ を覆う横のドミノである。残りは $2\times(n-2)$ の盤で、敷き詰め方は $a_{n-2}$ 通りある。
(1) と (2) は $(1,1)$ を覆うドミノの向きが違うので重ならない。よって
$$ a_n=a_{n-1}+a_{n-2}\qquad(n\ge3) $$
である。$a_1=1$、$a_2=2$ から順に $a_3=3$、$a_4=5$、$a_5=8$、$a_6=13$、$a_7=21$、$a_8=34$ となる。これは Fibonacci数列 と同じ漸化式である。

6 つのマス $(1,2)$、$(2,1)$、$(2,2)$、$(2,3)$、$(2,4)$、$(3,3)$ からなる盤を考える（図 5）。$r+c$ が偶数のマスは $(2,2)$、$(2,4)$、$(3,3)$ の 3 つ、奇数のマスは $(1,2)$、$(2,1)$、$(2,3)$ の 3 つで、市松模様の 2 色の個数はそろっている。
しかし、ドミノ 3 枚では敷き詰められない。マス $P=(2,1)$ に上下左右で隣り合う盤のマスは $R=(2,2)$ だけなので、$P$ を覆うドミノは $P$ と $R$ を覆うしかない。マス $Q=(1,2)$ に隣り合う盤のマスも $R$ だけなので、$Q$ を覆うドミノも $Q$ と $R$ を覆うしかない。$R$ を 2 枚のドミノで覆うことはできないので、敷き詰めはない。色の個数は必要条件にすぎず、形の細かいつながり方までは見ていない。

$10\times10$ の盤を市松模様に塗ると、余り $0$ と余り $1$ のマスは 50 個ずつある。$1\times4$ のタイルは 1 枚で余り $0$ と余り $1$ を 2 つずつ覆うので、lem-col-count の仮定「各色をちょうど 1 つずつ覆う」をみたさない。25 枚で覆えるとしても、覆う個数は各色 50 個ずつで、盤の個数と合う。つまり市松模様からは矛盾が出ず、thm-col-ten は示せない。一方で、矛盾が出ないことは敷き詰められることを意味しない。塗り分けによる証明では、タイルの形に合わせて、タイルが各色を同じ数だけ覆う塗り方を選ぶことが要になる。