§C5.2不変量と単調量

1 例1：市松模様の不変量

8×8の盤から左上と右下の2マスを取り除いた盤を、2マスのドミノで敷き詰めることはできません。市松模様に塗ると、取り除いた2マスは同じ色です。元の盤は黒32、白32ですが、取り除いた後は一色が30、他色が32。各ドミノは必ず黒1白1を覆うため、敷き詰め後の黒白個数は等しくなければならず、矛盾です。

面積が同じでも敷き詰められないことがあります。面積比較だけでは足りず、彩色という不変量を導入しています。

2 例2：偶奇不変量

整数の組$(a,b)$に対し、操作$(a,b)\mapsto(a+2,b-2)$を繰り返します。$a+b$は不変で、各成分の偶奇も変わりません。したがって、和が異なる組や偶奇型が異なる組へは到達できません。

操作問題では、まず「変わらない候補」を小さな法で調べます。mod 2、mod 3、和、積、差、彩色などが入口です。

3 例3：単調量で停止を示す

正整数の組に対する操作が、各回で正整数$N$を1以上減らすとします。$N$は下から0で抑えられているため、操作は無限には続きません。これは単調量の原理です。

無限降下は、停止性とは逆向きに「小さい同型の反例を作る」方法です。不変量・単調量・無限降下を、到達可能性、不可能性、停止性に応じて使い分けます。

4 不変量の探し方

• 操作が足し引き：和、差、mod を調べる。
• 交換や移動：彩色、位置の偶奇、順序を調べる。
• 置換：符号、転倒数、巡回構造を調べる。
• 数の因数変化：素因数の指数、最大公約数を調べる。

不変量が一つ見つからなければ、複数の不変量を組にしてもよいです。

5 演習

1. 盤の2マスを取り除く問題で、取り除く位置によって可能・不可能がどう変わるか分類せよ。
2. 3つの整数のうち2つを選び、両方に1を足す操作を繰り返す。3数の偶奇の組に関する不変量を調べよ。
3. ある操作で正整数の最大値が毎回減ることを示せば、操作が停止する理由を説明せよ。