Project Euler Problem 364
There are N seats in a row.
Solution
Answer: 44855254
Let the seats chosen in rule 1 (i.e. while a seat with no occupied neighbours still exists) form a set $S$.
A few key observations:
- The seats in $S$ are never adjacent.
- When rule 1 finishes, every remaining empty seat must be adjacent to at least one occupied seat.
Therefore $S$ is a maximal independent set of a path of length $N$.
Such configurations are completely determined by:
- $a$: the number of internal gaps of length $2$,
- $b\in{0,1,2}$: the number of empty end seats.
If $|S|=k$, then
$$N = 2k-1+a+b$$
so
$$k=\frac{N+1-a-b}{2}.$$
For fixed $(a,b)$:
- choose which of the $k-1$ internal gaps have length $2$:
$$\binom{k-1}{a}$$
- choose which ends are empty:
$$\binom{2}{b}$$
- order the $k$ rule-1 placements:
$$k!$$
- in each length-2 gap, either empty seat may be chosen during rule 2:
$$2^a$$
- the rule-2 placements can occur in any order:
$$(a+b)!$$
- the remaining seats (rule 3) can then be filled arbitrarily:
$$(N-k-a-b)!$$
Hence
$$T(N)= \sum_{a,b} \binom{k-1}{a} \binom{2}{b} k!, 2^a, (a+b)!, (N-k-a-b)!,$$
with
$$k=\frac{N+1-a-b}{2}.$$
Implementing this modulo $100000007$ reproduces the checks:
- $T(10)=61632$
- $T(1000)\equiv 47255094 \pmod{100000007}$
and finally gives
$$T(1,000,000)\equiv 44855254 \pmod{100000007}.$$
Answer: 44855254