Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /235 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

On an infinite checkerboard, the union of any two distinct unit squares is called a (disconnected) domino. A domino is said to be of type (a,b)(a, b), with a≤ba \leq b integers not both zero, if the centers of the two squares are separated by a distance of aa in one orthogonal direction and bb in the other. (For instance, an ordinary connected domino is of type (0,1)(0,1), and a domino of type (1,2)(1,2) contains two squares separated by a knight's move.)

Figure 1

Each of the three pairs of squares above forms a domino of type (1,2)(1,2).

Two dominoes are said to be congruent if they are of the same type. A rectangle is said to be (a,b)(a, b)-tileable if it can be partitioned into dominoes of type (a,b)(a, b).

Let 0<m≤n0 < m \leq n be integers. How many different (i.e., noncongruent) dominoes can be formed by choosing two squares of an m×nm \times n array?

Solution

Solution:

We must have 0≤a<m0 \leq a < m, 0≤b<n0 \leq b < n, a≤ba \leq b, and aa and bb not both 00. The number of pairs (a,b)(a, b) with b<a<mb < a < m is m(m−1)/2m(m-1)/2, so the answer is
mn−m(m−1)2−1=mn−m2−m+22. m n - \frac{m(m-1)}{2} - 1 = m n - \frac{m^2 - m + 2}{2}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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