彩色論法は、対象を有限個の色に分類し、許された構成が色のバランスや色の変化と両立しないことを示す方法です。 彩色は見た目の補助ではなく、不変量を可視化したものです。
1 ドミノと市松模様
8×8盤の対角の2隅を取り除いた盤はドミノで敷き詰められません。市松模様では取り除いた2隅が同色で、残りの黒白マス数が異なります。ドミノ1枚は必ず異色の2マスを覆うため、敷き詰め後の色数が一致しなければならず矛盾です。
2 mod による彩色
整数をで割った余りを色の色とみなすと、足し算・掛け算の操作を色の変化として追跡できます。例えば、差がの倍数になる2数の存在は、余りの色で同色の2対象が生じる鳩の巣原理です。
3 グラフの彩色
頂点を2色に塗り、辺の両端を異色にする問題は、奇閉路の有無と結び付きます。奇閉路があれば交互彩色が一周で破綻します。逆に奇閉路がなければ、各連結成分で一つの頂点からの距離の偶奇で2色に塗れます。
4 色の選び方
- 移動が上下左右：市松模様や座標の偶奇。
- 数の操作：mod。
- 回転・反転：向き、符号、色の置換。
- 分割・敷き詰め：各部品がもつ色の寄与。
色を増やせば強くなるとは限りません。同じ部品の寄与が簡単に記述でき、初期配置と目標配置の違いが残る色数を選びます。
5 演習
- 8×8盤から同色の2マスを取り除いた場合、ドミノ敷き詰めの可能性を色数から判定せよ。
- 盤の隅を取り除く問題について、列の偶奇を使った不可能性条件を探せ。
- 奇閉路が2色彩色できない理由を、色を一周追跡して説明せよ。
- ある整数操作に対して有効なmod彩色を自分で設計し、到達不可能な状態を一つ示せ。