Maths Olympiad Prep

Library / /255 of 377

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 aba \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<mn0 < 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 0a<m0 \leq a < m, 0b<n0 \leq b < n, aba \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(m1)/2m(m-1)/2, so the answer is
mnm(m1)21=mnm2m+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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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