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 方块铺满，从而由第一步可用 hook 铺满。