MathLabs

第3問

六つの単位正方形からなる図形で、三個からなる一列と四個からなる一列が一つの角の正方形を共有し、さらにその行の遠い端にもう一つの正方形が付け加わったもの(またはこれを回転・鏡映して得られる図形)を hook と定義する。そのような hook で隙間も重なりもなく敷き詰められ、hook のどの部分も長方形の外に出ない m×nm\times n 長方形をすべて求めよ。
ステップ 3/6: 必要性:辺の長さ 1,2,51,2,5 を除外する
m or n∈{1,2,5}  ⟹  no hook fits without leftover cellsm\text{ or }n\in\{1,2,5\} \implies \text{no hook fits without leftover cells}
詳しい解説

hook は 3×33\times3 の外接枠に入るので、幅 11 または 22 の帯には置けない。幅 55 の場合は、一つの角と、その二つの境界辺に接する最初の二行・二列を調べる。角に接する hook の向きは、示されたマス配置を回転・鏡映した有限個だけであり、これらを調べると、二つの境界層にある hook のマスによって、この 3×33\times3 窓の反対側の角にある三マスのうち一つを次に覆わなければならない。その次の hook は最初の hook と重なるか、角の直隣の境界マスを覆い残す。したがって幅 55 の長方形の角を覆う敷き詰めは存在しないが、長方形には必ず四つの角がある。よって m,n∉{1,2,5}m,n\notin\{1,2,5\} が必要である。