# Duo Dominoes – Solution

→ Print-friendly version

Let’s take another look at that 2xn region.

So let’s look at n=1.

This case is pretty simple: there’s only room for one domino on this grid, and there’s only one way to place it.

Now let’s look at n=2.

This case is also pretty simple: there’s room for 2 dominoes side by side, and we could either place them both horizontally or both vertically. (In general, we can place n dominoes on a 2xn grid, since each domino covers 2 squares. And tiling a 2xn grid with n dominoes is always possible: just take the example of placing all the dominoes horizontally.)

Now let’s try n=3. After a bit of trial and error, we come up with these options:

Either they all go horizontally, or two of them pair up to go vertically (in which case, the remaining horizontal domino could go above or below the vertical ones). In fact, we can see that any vertical dominoes must come in pairs: two vertical ones side by side. (We can’t stagger the vertical ones – see if you can figure out why.)

When we try n=4, things get a little trickier, and we need to be more systematic. We could either start with a horizontal domino on the bottom:

Once we’ve made that initial choice, it’s easier to fill in the rest of the grid with all the different combinations.

Moving on to n=5… Looks like the horizontal-or-vertical trick we tried above is going to be useful here as well. If we start with a horizontal domino, then all we have left to tile is a 2×4 grid, and if we start with a pair of vertical dominoes, then all we’re left with is a 2×3 grid. We add the number of 2×3 options to the number of 2×4 options to get the number of 2×5 options.

This looks like a pattern that we can generalize!

Let’s call $D_n$ the number of ways there are to tile a 2xn grid. We can break down $D_n$ by the above strategy: either it has a horizontal domino at the bottom, which can happen $D_{n-1}$ ways since there’s a 2x(n-1) grid remaining, or it has a pair of vertical dominoes at the bottom, which can happen $D_{n-2}$ ways since there’s a 2x(n-2) grid remaining. Putting it all together,

$D_n = D_{n-1} + D_{n-2}$

And we already know that $D_1 = 1$ and $D_2 = 2$. So we can build the rest of the sequence:

$1, 2, 3, 5, 8, 13, \ldots$

Aha! We’ve uncovered the Fibonacci numbers! Specifically, $D_n$ is the (n+1)th Fibonacci number. This is just one example of how math that seems completely unrelated can pop up unexpectedly in a problem.