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 的 tile 数必须为偶数。交换行列即可同样得到类型 22 的 tile 数也为偶数。