HMMT 二月 2005 · TEAM2 赛 · 第 4 题

HMMT February 2005 — TEAM2 Round — Problem 4

[30] Prove that an m × n rectangle is ( b, b )-tileable if and only if 2 b | m and 2 b | n .

解析

[30] Prove that an m × n rectangle is ( b, b )-tileable if and only if 2 b | m and 2 b | n . Solution: Color the first b rows of an m × n rectangle black, the next b white, the next b black, etc. Any ( b, b ) domino covers one square of each color, so for the rectangle to be ( b, b )-tileable, there must be the same number of black squares as white squares. This is possible only when 2 b | m . Similarly, we must have 2 b | n . It is easy to exhibit a tiling of all such rectangles, proving the claim. (It is also possible to prove this using the lemma described below.)