IMO 1999 SL C2

Origin: CAN | Category: Combinatorics

Problem

(a) If a 5 \times n rectangle can be tiled using n pieces like those shown in the diagram, prove that n is even. (b) Show that there are more than 2\cdot3k−1 ways to tile a fixed 5\times2k rect- angle (k \geq3) with 2k pieces. (Symmetric constructions are considered to be different.)

Solution

(a) Color the first, third, and fifth row red, and the remaining squares white. There in total n pieces and 3n red squares. Since each piece can cover at most three red squares, it follows that each piece colors exactly three red squares. Then it follows that the two white squares it covers must be on the same row; otherwise, the piece has to cover

at least three. Hence, each white row can be partitioned into pairs of squares belonging to the same piece. Thus it follows that the number of white squares in a row, which is n, must be even. (b) Let ak denote the number of different tilings of a 5 \times 2k rectangle. Let bk be the number of tilings that cannot be partitioned into two smaller tilings along a vertical line (without cutting any pieces). It is easy to see that a1 = b1 = 2, b2 = 2, a2 = 6 = 2 \cdot 3, b3 = 4, and subsequently, by induction, b3k \geq4, b3k+1 \geq2, and b3k+2 \geq2. We also have ak = bk + k−1 i=1 biak−i. For k \geq3 we now have inductively ak > 2 + k−1  i=1 2ak−i \geq2 \cdot 3k−1 + 2ak−1 \geq2 \cdot 3k .