Project Euler Problem 191

Solution

Answer: 1918080160

Let a valid (“prize”) attendance string of length $n$ satisfy:

• no three consecutive $A$'s,
• at most one $L$.

We must count such strings for $n=30$.

---

Step 1 — Reformulating the problem

Each day can be:

• $O$ = on time,
• $A$ = absent,
• $L$ = late.

The constraints are:

1. No substring $AAA$,
2. At most one $L$.

This is a classic finite-state dynamic programming problem.

A clean way to solve it is:

• first count strings with no $L$,
• then insert exactly one $L$.

---

Step 2 — Count strings with no $L$

Define:

$$f(n)=\text{number of length-}n\text{ strings using only }O,A$$

with no three consecutive $A$'s.

We derive a recurrence.

A valid string of length $n$ must end in one of:

• $O$,
• $AO$,
• $AAO$,
• or possibly all $A$'s if short enough.

More systematically:

If the string ends with:

• $O$: preceding part contributes $f(n-1)$,
• $AO$: preceding part contributes $f(n-2)$,
• $AAO$: preceding part contributes $f(n-3)$.

Hence for $n\ge3$,

$$f(n)=f(n-1)+f(n-2)+f(n-3).$$

This is a Tribonacci recurrence.

Initial values:

$$f(0)=1$$

(empty string)

$$f(1)=2$$

($O,A$)

$$f(2)=4$$

($OO,OA,AO,AA$)

So:

$$f(3)=4+2+1=7.$$

Indeed the only invalid length-3 string is $AAA$.

---

Step 3 — Introduce the single $L$

Now count prize strings with at most one $L$.

Two cases:

---

Case 1: No $L$

There are simply:

$$f(30)$$

such strings.

---

Case 2: Exactly one $L$

Place the $L$ at position $k$ ($1\le k\le 30$).

Then:

• the left side has length $k-1$,
• the right side has length $30-k$,

and both sides are independent valid no-$L$ strings.

So the count is:

$$\sum_{k=1}^{30} f(k-1)f(30-k).$$

Therefore the total number of prize strings is

$$P(30)=f(30)+\sum_{k=1}^{30} f(k-1)f(30-k).$$

Equivalently:

$$P(30)=f(30)+\sum_{i=0}^{29} f(i)f(29-i).$$

---

Step 4 — Python implementation

def prize_strings(n):
    # f[i] = number of valid strings of length i
    # using only O and A, with no AAA
    f = [0] * (n + 1)

    # Base cases
    f[0] = 1
    if n >= 1:
        f[1] = 2
    if n >= 2:
        f[2] = 4

    # Tribonacci recurrence
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2] + f[i - 3]

    # Case 1: no L
    total = f[n]

    # Case 2: exactly one L
    for i in range(n):
        total += f[i] * f[n - 1 - i]

    return total

# Verify the example in the problem
print(prize_strings(4))   # should be 43

# Compute the required answer
print(prize_strings(30))

---

Step 5 — Code walkthrough

Building the array f

f = [0] * (n + 1)

Stores the number of valid no-$L$ strings of each length.

---

Base cases

f[0] = 1
f[1] = 2
f[2] = 4

These correspond to:

• length 0: empty string,
• length 1: $O,A$,
• length 2: all four binary strings.

---

Recurrence

f[i] = f[i - 1] + f[i - 2] + f[i - 3]

A valid string ends with:

• $O$,
• $AO$,
• $AAO$.

---

No-$L$ contribution

total = f[n]

Counts all valid strings without any late days.

---

Exactly one $L$

for i in range(n):
    total += f[i] * f[n - 1 - i]

Choose where the $L$ goes.

• Left side length = $i$,
• Right side length = $n-1-i$.

Multiply because the two sides are independent.

---

Step 6 — Verification on the small example

For $n=4$:

The program gives:

$$43$$

which matches the problem statement exactly.

---

Step 7 — Compute for $n=30$

The recurrence produces:

$$f(30)=53798080$$

and after adding the one-$L$ cases:

$$P(30)=1918080160.$$

This magnitude is reasonable:

• total unrestricted strings: $3^{30}\approx2.06\times10^{14}$,
• the constraints eliminate most strings,
• a result around $10^9$ is plausible.

---

Answer: 1918080160