Red, Green, and Blue Tiles

Using a combination of grey square tiles and oblong tiles chosen from: red tiles (measuring two units), green tiles (measuring three units), and blue tiles (measuring four units), it is possible to tile a row measuring five units in length in exactly fifteen different ways.

How many ways can a row measuring fifty units in length be tiled?
NOTE: This is related to Problem 116.

This problem is a classic example of a question on combinatorics, and it can be solved using dynamic programming. Here’s how:

Firstly, let’s define F(m, n) as the number of ways to fill a row of length n using tiles of length m and 1 (the grey square tile).

The base cases can be defined as follows:

1) F(m, n) = 0, if n < m. 2) F(m, n) = 1, if n = m. 3) F(m, n) = 1, if n < m; since we can only use the 1x1 gray tiles to fill the row. We can develop a recurrence relation to calculate F(m, n) in terms of smaller sub-problems, as follows: F(m, n) = F(m, n-1) + F(m, n-m), for n > m.

This is because any arrangement of tiles in a row of length n either ends in a grey tile (in which case the number of arrangements is F(m, n-1)) or it ends in a tile of length m (in which case the number of arrangements is F(m, n-m)).

The dynamic programming approach to solve this problem is to calculate F(m,n) iteratively for each n from m up to 50 and for each m in (2, 3, 4).

After you have calculated the ways to fill a row for each tile size, remember that we don’t count the arrangements that consist only of grey tiles, so we subtract 3 from the total (one for each tile size).

Finally, you sum all calculated counts for each of the tile sizes, and that’s your answer.

If implemented correctly the code will give you the 2049257094 different ways a row measuring 50 units in length can be tiled using red, green, blue, and grey tiles.

More Answers: