Solution

Answer: 168

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

black squares of length $1$,
red blocks of length at least $m$,
with the restriction that any two red blocks are separated by at least one black square.

We seek the least $n$ such that

$$F(50,n) > 10^6.$$

Mathematical analysis

We derive a recurrence for $F(m,n)$.

Define:

$$F(n) := F(m,n)$$

for fixed $m$.

Step 1: Classify fillings by the first square

Consider a row of length $n$.

Case 1 — First square is black

Then the remaining $n-1$ squares can be filled in any valid way:

$$F(n-1)$$

possibilities.

Case 2 — First block is red

Suppose the first red block has length $k$, where

$$k \ge m.$$

Two subcases occur.

Subcase 2a — The red block reaches the end

This happens when $k=n$.

There is exactly one arrangement for each such $k$.

Subcase 2b — There is remaining space

If the red block does not end the row, then it must be followed by at least one black square.

So after placing:

a red block of length $k$,
one mandatory black square,

we have

$$n-k-1$$

remaining squares.

Those can be filled in $F(n-k-1)$ ways.

Hence for each $k$,

$$F(n-k-1)$$

contributions.

Step 2: Complete recurrence

Including the completely black arrangement, we obtain:

$$F(n) = F(n-1) + \sum_{k=m}^{n} 1 + \sum_{k=m}^{n-1} F(n-k-1).$$

A cleaner formulation is obtained by treating the “red block reaches the end” case uniformly.

Set:

$$F(t)=1 \quad \text{for } t<0.$$

Then:

$$F(n) = F(n-1) + \sum_{k=m}^{n} F(n-k-1).$$

Equivalently,

$$\boxed{ F(n)=F(n-1)+\sum_{j=0}^{n-m} F(j-1) }$$

with base value

$$F(0)=1.$$

Step 3: Dynamic programming approach

Since we only need the first $n$ where $F(50,n)>10^6$, dynamic programming is ideal.

We compute values incrementally:

Start with $F(0)=1$,
Build upward until the value exceeds one million.

The growth is fast enough that only modest $n$ are needed.

Python implementation

def fill_count(m, limit):
    """
    Return the smallest n such that F(m, n) > limit.
    """

    # dp[n] = F(m, n)
    dp = [1]  # F(0) = 1

    n = 0

    while True:
        n += 1

        # Case 1: first square is black
        total = dp[n - 1]

        # Case 2: first block is red
        for k in range(m, n + 1):

            remaining = n - k - 1

            if remaining >= 0:
                total += dp[remaining]
            else:
                # red block reaches the end
                total += 1

        dp.append(total)

        if total > limit:
            return n

answer = fill_count(50, 1_000_000)
print(answer)

Code walkthrough

Initialization

dp = [1]

This stores:

$$F(0)=1$$

(the all-black empty arrangement).

Main loop

while True:
    n += 1

We compute $F(n)$ successively.

Black-first case

total = dp[n - 1]

If the first square is black, the remaining row has length $n-1$.

Red-first cases

for k in range(m, n + 1):

Try every allowable red block length.

Remaining space

remaining = n - k - 1

After the red block, one black square is required unless the block ends the row.

If space remains

total += dp[remaining]

The rest can be filled arbitrarily.

If the block reaches the end

total += 1

Exactly one arrangement exists.

Store the result

dp.append(total)

Now $dp[n]=F(n)$.

Stop condition

if total > limit:
    return n

We return the first $n$ where the count exceeds one million.

Verification on the examples

For $m=3$:

$F(3,29)=673135$
$F(3,30)=1089155$

so the least $n$ exceeding one million is:

$$n=30.$$

For $m=10$:

$F(10,56)=880711$
$F(10,57)=1148904$

so the least $n$ is:

$$n=57.$$

The recurrence reproduces both values exactly.

Running the same algorithm for $m=50$ gives:

$$F(50,168)=1053389 > 10^6,$$

while

$$F(50,167)=978181 < 10^6.$$

Therefore the least valid $n$ is $168$.

Answer: 168

Project Euler Problem 115