Olympiad Maths Prep

Library / /5 of 14

Combinatorics Difficulty 6.3 National olympiad Prove it Czech Republic

Determine the number of all coverings of a chessboard 3×103 \times 10 by (nonoverlapping) pieces 2×12 \times 1 which can be placed both horizontally and vertically.

Solution

Let us solve a more general problem of determining the number ana_n of all coverings of a chessboard 3×2n3 \times 2n by pieces 2×12 \times 1, for a given natural nn. We will attack the problem by a recursive method, starting with n=1n = 1.

The value a1=3a_1 = 3 (for the chessboard 3×23 \times 2) is evident (see Fig. 2). To prove that a2=11a_2 = 11 by a direct drawing all possibilities is too laborious. Instead of this, we introduce new numbers bnb_n: Let each bnb_n denote the number of all "incomplete" coverings of a chessboard 3×(2n1)3 \times (2n - 1) by 3n23n - 2 pieces 2×12 \times 1, when a fixed corner field 1×11 \times 1 (specified in advance, say the lower right one) remains uncovered. Thanks to the axial symmetry, the numbers bnb_n remain to be the same if the fixed uncovered corner field will be the upper right one. Moreover, it is clear that b1=1b_1 = 1.

Figure 1

Fig. 2

Now we are going to prove that for each n>1n > 1, the following equalities hold:
bn=an1+bn1andan=an1+2bn.(1) b_n = a_{n-1} + b_{n-1} \quad \text{and} \quad a_n = a_{n-1} + 2b_n. \quad (1)

Figure 2

Fig. 3

Similarly, the second equality in (1) follows from a partition of all coverings of a chessboard 3×2n3 \times 2n into three (disjoint) classes which are formed by coverings of types C, D and E respectively, see Fig. 4. It is evident that the numbers of elements in the three classes are an1a_{n-1}, bnb_n and bnb_n, respectively.

Figure 3

Fig. 4

Now we are ready to compute the requested number a5a_5. Since a1=3a_1 = 3 and b1=1b_1 = 1, the proved equalities (1) successively yield
b2=a1+b1=4,a2=a1+2b2=11,b3=a2+b2=15,a3=a2+2b3=41,b4=a3+b3=56,a4=a3+2b4=153,b5=a4+b4=209,a5=a4+2b5=571. \begin{aligned} b_2 &= a_1 + b_1 = 4, \quad a_2 = a_1 + 2b_2 = 11, \quad b_3 = a_2 + b_2 = 15, \quad a_3 = a_2 + 2b_3 = 41, \\ b_4 &= a_3 + b_3 = 56, \quad a_4 = a_3 + 2b_4 = 153, \quad b_5 = a_4 + b_4 = 209, \quad a_5 = a_4 + 2b_5 = 571. \end{aligned}

*Answer.* The number of coverings of the chessboard 3×103 \times 10 equals 571571.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.