HMMT 二月 2005 · TEAM1 赛 · 第 2 题

英文解析

2. [25] Suppose 0 < a ≤ b and 4 - mn . Prove that the number of ways in which an m × nrectangle can be partitioned into dominoes of type ( a, b ) is even.
   Solution: If the rectangle is tileable, it can be partitioned into an odd number ofdominoes. Consider the reflection of the partitioned rectangle over one axis. Thisgives another partition of the rectangle. In fact, it cannot be the same partition, forsuppose it were. Then we can pair each domino with its reflected image, but sincethere are an odd number of dominoes, one must reflect into itself. Since a > 0, this isnot possible. Therefore, we can pair off partitions and their reflections, and it followsthat the total number of partitions is even. 1