敷き詰めパズルと不変量

イントロ

全部試さずに「不可能」を示す

操作で変わらない量を見つける

敷き詰めを何度試しても失敗するだけでは、不可能の証明になりません。盤面を二種類に分け、どの置き方でも変わらない関係を見つけると、すべての配置を一度に除外できます。個別の試行から一般の根拠へ進む見方です。

定義

教科書では: 操作を繰り返しても値や関係が変わらないように選んだ量です。
言いかえると: 8×8盤を市松模様にA・Bの二種類で塗ると、縦横に隣り合うマスは必ず異なる種類です。1×2ドミノは隣接2マスを覆うため、向きに関係なくAを1マス、Bを1マス覆います。そこでAとBの個数差が、すべての置き方を調べる代わりの不変量になります。

要点

問題の操作が毎回どんなマスを使うかに注目し、それを数えやすい分類へ置き換えます。分類は見た目ではなく、操作との関係で選びます。

手順

例

場面: 8×8盤の左上と右下の隅を除き、残り62マスを31枚のドミノで覆えるか。
順に考えると: 元の盤にはAとBが32マスずつあります。左上と右下は同じ種類Aなので、除いた後はAが30、Bが32です。31枚のドミノならAとBを31ずつ覆う必要がありますが、Aは30しかありません。向きを変えても一枚が覆うA・Bの組は変わらないため、どんな配置でも矛盾し、敷き詰められません。
ここが結論: 面積62が偶数であることは必要条件にすぎません。A・Bの個数が等しいという、より強い必要条件を満たさないことが決定的です。必要条件を一つ満たしても十分とは限りません。

注意

確認

Q1

同色の対角隅2マスを除いた盤をドミノで覆えない決め手はどれですか。

まとめ

三目並べの盤面を状態として読み、勝ち・防御・次の脅威の順に一手を評価し、選択理由を説明します。