Project Euler Problem 117

Solution

Answer: 100808458960497

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

• grey squares of length $1$,
• red oblongs of length $2$,
• green oblongs of length $3$,
• blue oblongs of length $4$.

We want $F(50)$.

---

Mathematical analysis

Step 1: Build the recurrence

Consider the leftmost tile in a valid tiling of length $n$.

There are four possibilities:

1. A grey square of length $1$

Remaining length: $n-1$ 2. A red tile of length $2$

Remaining length: $n-2$ 3. A green tile of length $3$

Remaining length: $n-3$ 4. A blue tile of length $4$

Remaining length: $n-4$

Therefore,

$$F(n)=F(n-1)+F(n-2)+F(n-3)+F(n-4)$$

This is a generalized Fibonacci recurrence.

---

Step 2: Determine base cases

We define:

$$F(0)=1$$

Why? Because there is exactly one way to tile a row of length $0$: use no tiles.

Now compute small values:

$n=1$

Only one possibility:

• $1$

So:

$$F(1)=1$$

---

$n=2$

Possibilities:

• $1+1$
• $2$

Thus:

$$F(2)=2$$

---

$n=3$

Possibilities:

• $1+1+1$
• $1+2$
• $2+1$
• $3$

Hence:

$$F(3)=4$$

---

$n=4$

Possibilities:

• $1+1+1+1$
• $2+1+1$
• $1+2+1$
• $1+1+2$
• $2+2$
• $3+1$
• $1+3$
• $4$

So:

$$F(4)=8$$

The recurrence now generates all later values.

---

Step 3: Verify the example $n=5$

Using the recurrence:

$$F(5)=F(4)+F(3)+F(2)+F(1)$$

$$F(5)=8+4+2+1=15$$

which matches the problem statement.

---

Python implementation

def count_tilings(n):
    # dp[i] = number of tilings of length i
    dp = [0] * (n + 1)

    # Base case:
    # one way to tile an empty row
    dp[0] = 1

    for i in range(1, n + 1):
        # Place a grey tile of length 1
        dp[i] += dp[i - 1]

        # Place a red tile of length 2
        if i >= 2:
            dp[i] += dp[i - 2]

        # Place a green tile of length 3
        if i >= 3:
            dp[i] += dp[i - 3]

        # Place a blue tile of length 4
        if i >= 4:
            dp[i] += dp[i - 4]

    return dp[n]

print(count_tilings(50))

---

Code walkthrough

Function definition

def count_tilings(n):

Defines a function that computes the number of tilings for length $n$.

---

DP array

dp = [0] * (n + 1)

Creates an array where:

$$dp[i] = F(i)$$

---

Base case

dp[0] = 1

There is one way to tile an empty row.

---

Main loop

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

Compute values from smaller lengths upward.

---

Add contributions from each tile type

Grey tile

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

If the first tile has length $1$, the remainder has length $i-1$.

---

Red tile

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

Similarly for length $2$.

---

Green tile

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

---

Blue tile

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

---

Return result

return dp[n]

Returns the desired count.

---

Small-value verification

The recurrence generates:

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

The problem explicitly states there are $15$ tilings for length $5$, so our recurrence is correct.

Continuing the recurrence up to $50$ gives:

$$F(50)=100808458960497$$

---

Final verification

The sequence grows exponentially, so a $15$-digit answer for $n=50$ is reasonable.

The recurrence is exhaustive and non-overlapping:

• every tiling begins with exactly one of the four tile types,
• and each choice reduces to a smaller independent subproblem.

Thus the computation is correct.

---

Answer: 100808458960497