MathLabs

第3問

六つの単位正方形からなる図形で、三個からなる一列と四個からなる一列が一つの角の正方形を共有し、さらにその行の遠い端にもう一つの正方形が付け加わったもの（またはこれを回転・鏡映して得られる図形）を hook と定義する。そのような hook で隙間も重なりもなく敷き詰められ、hook のどの部分も長方形の外に出ない m×nm\times n 長方形をすべて求めよ。
ステップ 2/6: 十分性：3×43\times4 ブロックから長方形を組み立てる
前のステップ次のステップ
3∣m, 4∣n  ⟹  m×n tiled by 3×4 blocks;3∣m,4∤m,3∤n,4∤n  ⟹  12∣m, n≥7=3a+4b3\mid m,\ 4\mid n \implies m\times n\text{ tiled by }3\times4\text{ blocks};\quad 3\mid m,4\nmid m,3\nmid n,4\nmid n\implies 12\mid m,\ n\ge7=3a+4b
詳しい解説

3∣m3\mid m かつ 4∣n4\mid n なら、長方形を直接 3×43\times4 ブロックの格子に分割する。そうでなくても、二つの仮定 3∣m or 3∣n, 4∣m or 4∣n3\mid m\text{ or }3\mid n,\ 4\mid m\text{ or }4\mid n から少なくとも一方の辺、例えば 12∣m12\mid m、について mm が成り立つ。m,n∉{1,2,5}m,n\notin\{1,2,5\} なので n≥3n\ge3 となり、nn は非負整数 n=3a+4bn=3a+4b を用いて a,b≥0a,b\ge0 と書け、mm 方向は幅 33 または 44 の帯に分割され、それぞれ端から端まで並べた 3×43\times4 ブロックの合併になる（12∣m12\mid m を用いる）。いずれにせよ長方形全体が 3×43\times4 ブロックで敷き詰められ、ステップ1により hook でも敷き詰められる。