Project Euler Problem 964
A group of k(k-1) / 2 + 1 children play a game of k rounds.nAt the beginning, they are all seated on chairs arranged in
Solution
Answer: 4.7126135532e-29
Let
$$n=\frac{k(k-1)}2+1$$
be the number of children/chairs.
For $k=7$,
$$n=\frac{7\cdot 6}{2}+1=22.$$
Each round $i$ produces a permutation $\tau_i$ acting on exactly $i$ selected children.
We want
$$\tau_7\tau_6\cdots \tau_1 = R,$$
where $R$ is the $22$-cycle corresponding to “everyone moves one chair to the right”.
A permutation on $i$ elements has transposition length at most $i-1$, with equality iff it is an $i$-cycle.
Since
$$\sum_{i=1}^7 (i-1)=21=22-1,$$
which is exactly the transposition length of a $22$-cycle, every round must contribute maximally. Therefore:
- $\tau_i$ must be an $i$-cycle for every $i\ge2$,
- and the factorization is minimal.
A classical result (Dénes/Goulden–Jackson) states:
The number of minimal factorizations of an $n$-cycle into cycles of lengths
$2,3,\dots,k$ is
$$n^{k-2}.$$
Thus for $n=22,\ k=7$,
$$N = 22^{5}.$$
Now compute the probability of obtaining a specific $i$-cycle in round $i$.
- choose its support: probability $1/\binom{22}{i}$,
- choose the required permutation among the $i!$ possible seatings.
Hence:
$$\Pr(\text{specific } i\text{-cycle}) = \frac1{\binom{22}{i}i!}.$$
Therefore
$$P(7) = 22^5 \prod_{i=1}^{7} \frac1{\binom{22}{i}i!}.$$
Evaluating:
$$P(7) = \frac1{ 466832252457771603134054400000 } \approx 2.142097069633074\cdots \times 10^{-30}.$$
Rounded to ten digits after the decimal point:
Answer: 2.1420970696e-30