Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A strip of rows and columns is covered with tiles, with no gaps and no overlaps. Two kinds of tile are allowed: a domino of cells, which may lie flat or stand upright, and a square of cells.
Let be the number of coverings. Set up a recurrence by looking at the left end of the strip, and find and . Then solve the recurrence with its characteristic equation, and find . Check your formula against the recurrence for small .
Name the count . Split on the first or the last step so that each case is a smaller copy of the same question. Check that the cases do not overlap and cover everything, then find the starting values by hand.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Split on the tiles at the left end, then solve.
Step 1. The left end. An upright domino leaves a strip. Two flat dominoes, one above the other, leave a strip, and so does a square. So .
Step 2. Starting values. (one upright domino). (two upright, two flat, or a square). It helps to put , which fits .
Step 3. Solve. gives the roots and , so . From and : and , so and . Hence .
Step 4. Check. The formula gives and , and the recurrence gives .
Step 5. The answer. .
Answer: coverings.
Log in to join the discussion.
Loading…