MathLabs

第3問

六つの単位正方形からなる図形で、三個からなる一列と四個からなる一列が一つの角の正方形を共有し、さらにその行の遠い端にもう一つの正方形が付け加わったもの（またはこれを回転・鏡映して得られる図形）を hook と定義する。そのような hook で隙間も重なりもなく敷き詰められ、hook のどの部分も長方形の外に出ない m×nm\times n 長方形をすべて求めよ。
ステップ 5/6: 二種類の tile に関する彩色論法
前のステップ次のステップ
color every 4th column red:#red cells covered by a type-1 tile is odd, by a type-2 tile is even  ⟹  #type-1 tiles is even\text{color every 4th column red}: \#\text{red cells covered by a type-1 tile is odd, by a type-2 tile is even} \implies \#\text{type-1 tiles is even}
詳しい解説

種別 11 では二つの hook の合併が連続する四列を占め、各列にはちょうど 33 マスがある。また tile が触れる各行には 22 または 44 マスがある。種別 22 は行と列を入れ替えたもので、連続する四行を占め、各行に 33 マスがあり、触れる各列には 22 または 44 マスがある。列番号が 44 の倍数の列を赤く塗る。以下で必要となる場合、二辺がともに偶数なので長方形の赤マス総数は偶数である。種別 11 の tile は四列ごとの組からちょうど一列に出会い、赤マスをちょうど 33 個覆うので奇数個である。種別 22 は出会う赤い列ごとに 22 または 44 マスを覆うので、赤マス数は偶数である。tile が長方形を分割するため、種別 11 の個数は偶数である。行と列を交換すれば、種別 22 の個数についても同じ結論を得る。