How many ways are there to cover a 3×8 rectangle with 12 identical dominoes?
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Trivially there is 1 way to tile a 3×0 rectangle, and it is not hard to see there are 3 ways to tile a 3×2. Let Tn be the number of tilings of a 3×n rectangle, where n is even. From the diagram below we see the recursion Tn=3Tn−2+2(Tn−4+Tn−6+…+T2+T0). Given that, we can just calculate T4=11,T6=41, and T8 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 reproduced verbatim; metadata (topic, difficulty) added by this project.