HMMT 二月 2005 · TEAM1 赛 · 第 2 题
HMMT February 2005 — TEAM1 Round — Problem 2
题目详情
- [25] Suppose 0 < a ≤ b and 4 - mn . Prove that the number of ways in which an m × n rectangle can be partitioned into dominoes of type ( a, b ) is even.
解析
- [25] Suppose 0 < a ≤ b and 4 - mn . Prove that the number of ways in which an m × n rectangle 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 of dominoes. Consider the reflection of the partitioned rectangle over one axis. This gives another partition of the rectangle. In fact, it cannot be the same partition, for suppose it were. Then we can pair each domino with its reflected image, but since there are an odd number of dominoes, one must reflect into itself. Since a > 0, this is not possible. Therefore, we can pair off partitions and their reflections, and it follows that the total number of partitions is even. 1