MathLabs

Problem 3

Define a hook to be a figure made up of six unit squares consisting of a row of three squares and a column of four squares sharing a corner square, together with one further square attached at the far end of the row (or any figure obtained from this one by rotations and reflections). Determine all m×nm\times n rectangles that can be covered without gaps and without overlaps by such hooks, with no part of a hook covering area outside the rectangle.
Step 2 of 6: Sufficiency: build the rectangle from 3×43\times4 blocks
Previous stepNext step
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
Detailed analysis

If 3∣m3\mid m and 4∣n4\mid n, partition the rectangle directly into a grid of 3×43\times4 blocks. Otherwise the two hypotheses 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 still give 12∣m12\mid m for at least one of the two side lengths, say mm; since m,n∉{1,2,5}m,n\notin\{1,2,5\}, we have n≥3n\ge3, so nn can be written as n=3a+4bn=3a+4b for nonnegative integers a,b≥0a,b\ge0, and the mm-direction splits into strips of width 33 or 44 which are each unions of 3×43\times4 blocks placed end to end (using 12∣m12\mid m). Either way the whole rectangle is tiled by 3×43\times4 blocks, hence by hooks via Step 1.