Project Euler Problem 584

A long long time ago in a galaxy far far away, the Wimwians, inhabitants of planet WimWi, discovered an unmanned drone t

Project Euler Problem 584

Solution

Answer: 32.83822408

Let $T$ be the number of people in the room when we first obtain 4 birthdays within 7 days of each other on a circular 365-day calendar.

The key observation is:

  • “Within 7 days of each other” means all 4 birthdays lie inside some block of $8$ consecutive calendar days.
  • Since birthdays wrap around the end of the year, the calendar is cyclic.

Define

$$S_n=\Pr(T>n),$$

the probability that after $n$ people, no block of $8$ consecutive days contains $4$ or more birthdays.

Then

$$\mathbb E[T]=\sum_{n\ge0} S_n.$$

So the problem reduces to counting birthday configurations avoiding the forbidden pattern.


1. Counting valid configurations

Let $c_i$ be the number of birthdays on day $i$, where $i=1,\dots,365$.

The condition “no 4 birthdays within 7 days” is exactly

$$c_i+c_{i+1}+\cdots+c_{i+7}\le 3$$

for every cyclic block of 8 consecutive days.

For a fixed occupancy vector $(c_1,\dots,c_{365})$ with total $n$,

$$\sum_i c_i=n,$$

the number of labeled birthday assignments realizing it is

$$\frac{n!}{\prod_i c_i!}.$$

Hence

$$S_n = \frac{n!}{365^n} \sum_{\substack{(c_i)\ \text{all 8-block sums }\le3\ \sum c_i=n}} \frac1{\prod_i c_i!}.$$


2. Transfer-state dynamic programming

To enforce the 8-day constraint, scan the calendar day-by-day.

A state stores the occupancies of the previous 7 days:

$$(c_{i-6},\dots,c_i).$$

When adding a new day with occupancy $x$, we require

$$x+c_{i-6}+\cdots+c_i \le 3.$$

Thus the total number of states is small:

$$\binom{7+3}{7}=120.$$

We build a transfer graph between states, weighted by

$$\frac{z^x}{x!}.$$

Because the calendar is cyclic, valid yearly configurations correspond to closed walks of length $365$.

Extracting the coefficient of $z^n$ gives the weighted count for $S_n$.

Finally,

$$\mathbb E[T] = \sum_{n\ge0} S_n.$$


3. Python implementation

from math import factorial
import numpy as np

DAYS = 365
GROUP = 4
WINDOW = 7
MAX_N = 100   # far beyond where probabilities become negligible

def generate_states(length, limit):
    """
    Generate all tuples of given length whose entries are
    nonnegative integers with total sum < limit.
    """
    states = []

    def dfs(pos, remaining, cur):
        if pos == length:
            states.append(tuple(cur))
            return

        for x in range(remaining):
            cur.append(x)
            dfs(pos + 1, remaining - x, cur)
            cur.pop()

    dfs(0, limit, [])
    return states

# State length = WINDOW = 7 previous days
states = generate_states(WINDOW, GROUP)

index = {s: i for i, s in enumerate(states)}
S = len(states)

# Build transitions
transitions = [[] for _ in range(S)]

for s in states:
    i = index[s]
    current_sum = sum(s)

    # occupancy on next day
    for x in range(GROUP - current_sum):

        next_state = s[1:] + (x,)
        j = index[next_state]

        weight = 1.0 / factorial(x)

        transitions[i].append((j, x, weight))

# dp[start_state, current_state, n]
dp = np.zeros((S, S, MAX_N + 1), dtype=np.float64)

for i in range(S):
    dp[i, i, 0] = 1.0

# advance through all 365 days
for _ in range(DAYS):

    ndp = np.zeros_like(dp)

    for s in range(S):

        arr = dp[:, s, :]

        for ns, x, w in transitions[s]:

            ndp[:, ns, x:] += arr[:, :MAX_N + 1 - x] * w

    dp = ndp

# closed walks give cyclic configurations
A = np.zeros(MAX_N + 1)

for i in range(S):
    A += dp[i, i, :]

# survival probabilities
survival = np.zeros(MAX_N + 1)

for n in range(MAX_N + 1):
    survival[n] = factorial(n) * A[n] / (DAYS ** n)

expected_value = survival.sum()

print(expected_value)
print(round(expected_value, 8))

4. Verification on the examples

The same program gives:

  • WimWi case (10 days, 3 people within 1 day):

$$5.78688636$$

matching the statement.

  • Joka case (100 days, 3 people within 7 days):

$$8.48967364$$

also matching the statement.

Thus the model is correct.


5. Earth case

Running the program for:

  • 365-day year
  • first occurrence of 4 birthdays
  • within 7 days

gives

$$32.83822407715108\ldots$$

Rounded to 8 decimal places:

$$32.83822408$$

Answer: 32.83822408