HMMT 二月 2005 · TEAM2 赛 · 第 4 题

英文解析

4. [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 nextb black, etc. Any ( b, b ) domino covers one square of each color, so for the rectangle tobe ( 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 exhibita tiling of all such rectangles, proving the claim. (It is also possible to prove this usingthe lemma described below.)