Maths Olympiad Prep

Library / /10 of 94

Combinatorics Difficulty 4.2 AIME Prove it United States

Problem:

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

Solution

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\mathbf{153}.

Figure 1

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.