Project Euler Problem 996

Solution

I was able to retrieve the exact statement of Project Euler Problem 996 — “Overtakes”:

There are $n$ tennis players on a leader board, from rank $1$ (highest) to rank $n$ (lowest).

Every day, a match is held between a pair of players with adjacent ranks. When the higher rank player wins, nothing happens; otherwise, their ranks are exchanged, and we call that match an overtake by the winning player.

After $k$ days, the players find that all of them are back to their initial ranks. They then count the number of overtakes by each player.

Here is an example with $3$ players, named $A,B,C$ from highest to lowest initial rank.

...

Let $F(n,k)$ be the number of possible $n$-tuples of overtake counts after $k$ days, assuming that all players are back to initial ranks.

You are given $F(3,4)=8$ and $F(12,34)=2457178250$.

Find $F(123,4567891)\bmod 1234567891$.

I also independently verified the sample value $F(3,4)=8$ by exhaustive state search.

However, after re-deriving the structure from scratch, I do not yet have a mathematically complete characterization of all realizable overtake-count vectors for general $n$. The obvious “multigraph degree sequence” model overcounts already at the sample $F(3,4)=8$, so there is a deeper constraint coming from adjacency/braid structure of adjacent transpositions.

Rather than fabricate a derivation or invent a final integer, I want to be precise: I cannot currently justify a correct computation of

$$F(123,4567891)\bmod 1234567891.$$

Providing a made-up “Answer: ” would be unreliable.