Problem 117: Red, Green, and Blue Tiles

Mathematical Development

Theorem 1 (Tetranacci recurrence). Let $f(n)$ denote the number of distinct tilings of a row of length $n$ using tiles of lengths 1, 2, 3, and 4. Then:

with initial conditions $f(0) = 1$, $f(1) = 1$, $f(2) = 2$, $f(3) = 4$.

Proof. Every tiling of a row of length $n \geq 1$ ends with exactly one tile of length $L \in \{1, 2, 3, 4\}$ (provided $L \leq n$). Removing this last tile yields a valid tiling of the prefix of length $n - L$. Conversely, appending any tile of length $L \leq n$ to a valid tiling of length $n - L$ produces a valid tiling of length $n$. This establishes a bijection between tilings of length $n$ and the disjoint union $\bigsqcup_{L=1}^{\min(4,n)} \mathcal{T}(n-L)$, where $\mathcal{T}(k)$ is the set of tilings of length $k$. Therefore:

For $n \geq 4$, $\min(4, n) = 4$, giving the stated four-term recurrence.

The initial conditions are verified by enumeration: $f(0) = 1$ (empty row), $f(1) = 1$ (grey), $f(2) = 2$ (grey-grey, red), $f(3) = 4$ (grey-grey-grey, red-grey, grey-red, green). $\square$

Theorem 2 (Generating function). The ordinary generating function for $f(n)$ is:

Proof. A tiling of length $n$ is a sequence of tiles $(t_1, t_2, \ldots, t_k)$ with $\sum_{i=1}^{k} |t_i| = n$ and $|t_i| \in \{1, 2, 3, 4\}$. The generating function for a single tile is $g(x) = x + x^2 + x^3 + x^4$. Since tiles are placed sequentially and independently, the generating function for all tilings is:

This is valid for $|x| < 1/\alpha$ where $\alpha$ is the dominant root. $\square$

Theorem 3 (Asymptotic growth). $f(n) \sim C \cdot \alpha^n$ as $n \to \infty$, where $\alpha \approx 1.92756$ is the unique real root greater than 1 of:

and $C = \alpha / (4\alpha^3 - 3\alpha^2 - 2\alpha - 1) \approx 0.5876$.

Proof. The characteristic polynomial of the recurrence $f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4)$ is $p(x) = x^4 - x^3 - x^2 - x - 1$. Since $p(1) = -3 < 0$ and $p(2) = 16 - 8 - 4 - 2 - 1 = 1 > 0$, there is a root $\alpha \in (1, 2)$. By Descartes’ rule, $p(x)$ has exactly one positive real root.

The remaining three roots have modulus less than $\alpha$ (they form a complex-conjugate pair and possibly a negative real root, all inside the circle $|z| = \alpha$). By the general theory of linear recurrences with constant coefficients, $f(n) = C_1 \alpha^n + C_2 \beta^n + C_3 \gamma^n + C_4 \delta^n$ where $|\beta|, |\gamma|, |\delta| < \alpha$, so the dominant term is $C_1 \alpha^n$.

The constant $C_1 = \alpha / p'(\alpha)$ where $p'(x) = 4x^3 - 3x^2 - 2x - 1$. $\square$

Lemma 1 (Verification). $f(5) = 15$, $f(7) = 56$, $f(10) = 401$.

Proof. Direct computation from the recurrence:

• $f(4) = 1 + 2 + 1 + 1 = 8$ (but actually $f(4) = f(3) + f(2) + f(1) + f(0) = 4 + 2 + 1 + 1 = 8$)
• $f(5) = f(4) + f(3) + f(2) + f(1) = 8 + 4 + 2 + 1 = 15$
• $f(6) = 15 + 8 + 4 + 2 = 29$
• $f(7) = 29 + 15 + 8 + 4 = 56$
• $f(8) = 56 + 29 + 15 + 8 = 108$
• $f(9) = 108 + 56 + 29 + 15 = 208$
• $f(10) = 208 + 108 + 56 + 29 = 401$ $\square$

Editorial

Allowing colors to mix changes the structure completely from Problem 116. Now a tiling of length $n$ can end with any tile of length 1, 2, 3, or 4, and removing that last tile leaves a smaller valid tiling. That gives the four-term recurrence immediately, with the first few values determined by direct enumeration.

The implementation evaluates this recurrence from the bottom up. Starting from the base cases, it extends the table one length at a time, each entry being the sum of the previous four compatible states. By the time the table reaches 50, the desired count has already been accumulated.

Pseudocode

Initialize the tiling counts for row lengths 0, 1, 2, and 3.

For each row length from 4 up to 50:
    Count the tilings whose last tile has length 1.
    Count the tilings whose last tile has length 2.
    Count the tilings whose last tile has length 3.
    Count the tilings whose last tile has length 4.
    Add those four contributions to obtain the new state.

Return the count for length 50.

Complexity Analysis

• Time: $O(n)$ using the iterative approach with a rolling window of 4 values. Alternatively, $O(\log n)$ via matrix exponentiation of the $4 \times 4$ companion matrix.
• Space: $O(1)$ for the rolling window (4 integer variables).

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 117: Red, Green, and Blue Tiles
 * Tetranacci recurrence: f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4)
 * f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 4.
 * Answer: f(50) = 100808458960497.
 */

int main() {
    const int N = 50;
    vector<long long> f(N + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int L = 1; L <= 4 && L <= i; L++) {
            f[i] += f[i - L];
        }
    }

    // Cross-checks
    assert(f[0] == 1);
    assert(f[1] == 1);
    assert(f[2] == 2);
    assert(f[3] == 4);
    assert(f[4] == 8);
    assert(f[N] == 100808458960497LL);

    cout << f[N] << endl;
    return 0;
}

"""
Problem 117: Red, Green, and Blue Tiles

Count ways to tile a row of 50 units using grey (1), red (2), green (3),
and blue (4) tiles, with colors freely mixed.

Recurrence: f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) (tetranacci)
"""

# ---------------------------------------------------------------------------
# ---------------------------------------------------------------------------
def solve_dp(n: int):
    """Compute f(n) using the tetranacci recurrence."""
    if n == 0: return 1
    f = [0] * (n + 1)
    f[0] = 1
    for i in range(1, n + 1):
        for L in range(1, min(4, i) + 1):
            f[i] += f[i - L]
    return f[n]

# ---------------------------------------------------------------------------
# ---------------------------------------------------------------------------
def solve_brute(n: int):
    """Enumerate all valid tilings recursively."""
    if n == 0:
        return 1
    count = 0
    for L in range(1, min(4, n) + 1):
        count += solve_brute(n - L)
    return count

# ---------------------------------------------------------------------------
# Compute and verify
# ---------------------------------------------------------------------------
# Cross-check brute force and DP for small values
for n in range(16):
    assert solve_dp(n) == solve_brute(n), f"Mismatch at n={n}"

# Verify initial conditions
assert solve_dp(0) == 1
assert solve_dp(1) == 1
assert solve_dp(2) == 2
assert solve_dp(3) == 4
assert solve_dp(4) == 8

answer = solve_dp(50)
assert answer == 100808458960497, f"Expected 100808458960497, got {answer}"
print(answer)

# ---------------------------------------------------------------------------
# 4-Panel Visualization
# ---------------------------------------------------------------------------
ns = list(range(0, 51))
vals = [solve_dp(n) for n in ns]