Track / Stage 4 / 184 of 340 #924 of 2444

Problem 924

AMC 12 late, AIME early

Combinatorics Difficulty 4.8 Prove it Harvard-MIT Mathematics Tournament · United States

Suppose $0 < a \leq b$ and $4 \nmid m n$ . Prove that the number of ways in which an $m \times n$ rectangle can be partitioned into dominoes of type $(a, b)$ is even.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.