Solution

Answer: 20492570929

Let $F_m(n)$ denote the number of ways to tile a row of length $n$ using:

grey squares of length $1$, and
coloured oblong tiles of a fixed length $m$,

with the condition that at least one coloured tile is used.

For this problem:

red tiles have length $2$,
green tiles have length $3$,
blue tiles have length $4$,

and colours cannot be mixed, so the final answer is

$$F_2(50)+F_3(50)+F_4(50).$$

Step 1 — Deriving the recurrence

Fix a tile length $m$.

We first count all tilings (including the all-grey arrangement), then subtract $1$ at the end.

Let

$$T_m(n)$$

be the total number of tilings of a row of length $n$ using:

grey squares of length $1$,
coloured tiles of length $m$.

We derive a recurrence from the leftmost position.

Case analysis

Consider the first tile.

Case 1: First tile is grey

Then we consume one unit, leaving a row of length $n-1$:

$$T_m(n-1).$$

Case 2: First tile is coloured

A coloured tile occupies $m$ units, leaving a row of length $n-m$:

$$T_m(n-m).$$

These are the only possibilities, so for $n \ge m$,

$$T_m(n)=T_m(n-1)+T_m(n-m).$$

For small $n<m$, no coloured tile fits, so the only arrangement is all grey:

$$T_m(n)=1 \qquad (0\le n<m).$$

Also,

$$T_m(0)=1.$$

Finally, since the problem requires at least one coloured tile, we subtract the all-grey arrangement:

$$F_m(n)=T_m(n)-1.$$

The required answer is therefore

$$(T_2(50)-1)+(T_3(50)-1)+(T_4(50)-1).$$

Step 2 — Checking the example $n=5$

Red tiles ($m=2$)

Using

$$T_2(n)=T_2(n-1)+T_2(n-2),$$

with

$$T_2(0)=1,\quad T_2(1)=1,$$

we get:

$$\begin{aligned} T_2(2)&=2\ T_2(3)&=3\ T_2(4)&=5\ T_2(5)&=8 \end{aligned}$$

Thus

$$F_2(5)=8-1=7,$$

matching the statement.

Green tiles ($m=3$)

$$\begin{aligned} T_3(0)&=1\ T_3(1)&=1\ T_3(2)&=1\ T_3(3)&=2\ T_3(4)&=3\ T_3(5)&=4 \end{aligned}$$

Hence

$$F_3(5)=4-1=3.$$

Correct.

Blue tiles ($m=4$)

$$\begin{aligned} T_4(0)&=1\ T_4(1)&=1\ T_4(2)&=1\ T_4(3)&=1\ T_4(4)&=2\ T_4(5)&=3 \end{aligned}$$

$$F_4(5)=3-1=2.$$

Total:

$$7+3+2=12,$$

exactly as given.

Step 3 — Python implementation

def count_ways(n, m):
    """
    Count tilings of a row of length n using:
      - grey tiles of length 1
      - coloured tiles of fixed length m

    At least one coloured tile must be used.
    """

    # dp[i] = total tilings of length i, including all-grey
    dp = [0] * (n + 1)

    # Base case
    dp[0] = 1

    for i in range(1, n + 1):

        # Put a grey tile first
        dp[i] += dp[i - 1]

        # Put a coloured tile first (if it fits)
        if i >= m:
            dp[i] += dp[i - m]

    # Exclude the all-grey arrangement
    return dp[n] - 1

answer = (
    count_ways(50, 2) +
    count_ways(50, 3) +
    count_ways(50, 4)
)

print(answer)

Step 4 — Code walkthrough

Function definition

def count_ways(n, m):

Computes the number of valid tilings for a row of length n using coloured tiles of size m.

DP array

dp = [0] * (n + 1)

dp[i] stores the total number of tilings of length i, including the all-grey tiling.

Base case

dp[0] = 1

There is exactly one way to tile a row of length $0$: use nothing.

Main recurrence

for i in range(1, n + 1):

Build answers from small lengths upward.

Add grey-first arrangements

dp[i] += dp[i - 1]

Place a grey square first, leaving length i-1.

Add coloured-first arrangements

if i >= m:
    dp[i] += dp[i - m]

If a coloured tile fits, place it first and tile the remainder.

Remove all-grey case

return dp[n] - 1

The recurrence includes the arrangement with no coloured tiles, which the problem excludes.

Final computation

answer = (
    count_ways(50, 2) +
    count_ways(50, 3) +
    count_ways(50, 4)
)

We compute the contributions for red, green, and blue separately and add them.

Step 5 — Computing the values

The recurrence gives:

$$\begin{aligned} F_2(50) &= 20365011073 \ F_3(50) &= 122106096 \ F_4(50) &= 5453760 \end{aligned}$$

Therefore,

$$20365011073 + 122106096 + 5453760 = 20492570929.$$

Final verification

The value is positive and roughly dominated by the Fibonacci-like growth from size-2 tiles, which is expected.
The smaller contributions from lengths $3$ and $4$ are reasonable because larger tiles fit in fewer ways.
The sample case $n=5$ matches exactly.

Answer: 20492570929

Project Euler Problem 116