Tile away!

How many ways are there to completely cover a 10x2 grid with only 1x1 and 1x3 tiles?

Assumptions : Tiles must completely cover the area without overlapping, or going beyond the 10x2 boundary, and must be oriented in the same direction as the 10x2 grid.


The answer is 784.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Geoff Pilling
Jul 6, 2017

First off, since the 3x1 tiles only fit in one direction, the two 1x10 rows can be taken independently, and the problem boils down to figuring out how many ways a 10x1 grid can be tiled and then squaring it.

Let N n N_n be the number of ways to tile an nx1 grid.

For a 10x1 grid, the far left tile can either be a 1x1 or a 3x1, and the rest can be filled in either N 7 N_7 or N 9 N_9 ways. In other words:

N 10 = N 9 + N 7 N_{10} = N_9 + N_7

To generalize this, for n > 2 n > 2 ,

N n = N n 1 + N n 3 N_n = N_{n-1} + N_{n-3}

And clearly,

N 0 = N 1 = N 2 = 1 N_0 = N_1 = N_2 = 1

Solving,

N 10 = 28 N_{10} = 28

So, the total number of ways to tile a 2x10 grid is:

N t o t a l = N 10 2 = 784 N_{total} = N_{10}^2 = \boxed{784}

Typo in the last line......it should be 784 not 284....

Aaghaz Mahajan - 3 years, 3 months ago

Log in to reply

Thanks... Good eyes! I've fixed it.

Geoff Pilling - 3 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...