Maths Olympiad Prep

Library / /182 of 860

Combinatorics Difficulty 4.9 AIME Find the answer

How many ways are there to cover a 3×83 \times 8 rectangle with 12 identical dominoes?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Trivially there is 1 way to tile a 3×03 \times 0 rectangle, and it is not hard to see there are 3 ways to tile a 3×23 \times 2. Let TnT_{n} be the number of tilings of a 3×n3 \times n rectangle, where nn is even. From the diagram below we see the recursion Tn=3Tn2+2(Tn4+Tn6++T2+T0)T_{n}=3 T_{n-2}+2\left(T_{n-4}+T_{n-6}+\ldots+T_{2}+T_{0}\right). Given that, we can just calculate T4=11,T6=41T_{4}=11, T_{6}=41, and T8T_{8} is 153.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.