Solution to Problem #9

The problem was solved by Ross Millikan of San Mateo CA, Bert Sevenhant of Hasselt (Belgium), Philippe Fondanaiche of Paris (France), and Ken Duisenberg and Kirk Bresniker of Roseville CA. The first two counted all configurations as distinct (571 of these), while the third considered rotations (but not reflections) to be equivalent (291 of these). In addition to these results, the last two found a count of 156 if rotations and reflections are considered equivalent. There were essentially two methods of solution.

1. Here is Bert Sevenhant's solution (Philippe Fondanaiche's was similar):

Divide the 3 x 10 rectangle in 5 in the obvious way. This gives you 4 "in-between-lines". Then I call such a line "broken" whenever at least one tile crosses the line. The number of ways of filling an 3 x 2n (n>1) rectangle so that all lines are broken is 2. (Just put one tile "breaking" the first "in-between-line", and you will see everything follows.) The number of ways to fill a 3 x 2 is 3. (also easy to see) Now we can count per configuration of broken and not broken lines. (denote I for not broken and X for broken.)

IIII                         has 3^5 possibilities
XIII,IXII,IIXI,IIIX is 4 x 2   x 3^3
XXII,IXXI,IIXX         3 x 2   x 3^2
XIXI,XIIX,IXIX         3 x 2^2 x 3
IXXX,XXXI              2 x 2   x 3
XIXX,XXIX              2 x 2^2
XXXX                   2

The sum of these numbers is the answer (571).

2. Here is Ross Millikan's solution:

There are 571 ways to tile a 3x10 rectangle with 1x2 dominoes, counting reflections and rotations as different. The easiest way to calculate this is to define P(n), Q(n) and N(n) for n even as P(n) is the number of ways to tile a 3xn rectangle with the left hand 3x2 separable from the rest (that is, having a vertical line separating the rectangle into a 3x2 and 3x(n-2)). Q(n) is the number of ways to tile 3xn without the left hand 3x2 separable. N(n) is the total number of ways to tile 3xn = P(n) + Q(n).

By inspection P(2) = 3 and obviously Q(2) = 0. The recurrence is P(n+2) = 3*(P(n) + Q(n)) because there are three different 3x2 rectangles we can join to the left end of a 3xn to make a 3x(n+2). Q(n+2) = 2/3 * P(n) + Q(n) because there are two ways to make a 3xn (where n>2) with no vertical breaks. So we start with three rectangles with a 3x2 on the end and get two with a 3x4 (in the casenof P(n)) or start with two with a 3xn (with n>2) and get two with a 3x(n+2) on the end.

This gives the following table
n     P(n)      Q(n)     N(n)
2     3         0        3
4     9         2        11
6     33        8        41
8     123       30       153
10    459       112      571

The growth rate approaches a factor 3/2*(1+sqrt(3))

Back to the Archives

Back to the Math Department Homepage.