Maths
Dominoes on a 2 by 10 strip
In how many ways can you cover a 2 by 10 strip of squares with 1 by 2 dominoes, with no gaps or overlaps?
- Hint 1Try 2 by 1, 2 by 2 and 2 by 3 first and count by hand.
- Hint 2Look at the left-hand end. Either one domino stands upright there, or two lie flat on top of each other.
- Let f(n) be the number of tilings of a 2 by n strip.
- At the left end, an upright domino leaves a 2 by (n − 1) strip; two flat dominoes leave a 2 by (n − 2) strip. Nothing else fits.
- So f(n) = f(n − 1) + f(n − 2), with f(1) = 1 and f(2) = 2.
- f runs 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, so f(10) = 89.
Where it lands: 89
The trap: Counting cases by hand for n = 10 instead of finding the rule from the small cases.
What a tutor might ask next: Why can a single flat domino at the left end never work on its own?
Now do one out loud. In the interview you think aloud with a tutor. Try a Maths problem with hints, follow-ups and Mia's feedback on how you think.