Let $k$ be a positive integer. A spectator is given $n=k!+k−1$ balls numbered $1,2,\dotsc,n$. Unseen by the illusionist, the spectator arranges the balls into a sequence as they see fit. The assistant studies the sequence, chooses some block of $k$ consecutive balls, and covers them under their scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the $k$ balls they do not see.
Devise a strategy for the illusionist and the assistant to follow so that the trick always works.
(The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes $k$ and the obscured sequence as input and then runs in time polynomial in $n$. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)
Source: Komal, October 2019, problem A $760$.
Proposed by Nikolai Beluhov, Bulgaria, and Palmer Mebane, USA
I can prove that such a strategy must exist:
We have a set $A$ of all permutations (what assistant sees) and a set $B$ of all possible positions of a scarf (mark it $0$) and remaining numbers (what the illusionist sees).
We connect each $a$ in $A$ with $b$ in $B$ if a sequence $b$ without $0$ matches with some consecutive subsequence in $a$. Then each $a$ has degree $n-k+1$ and each $b$ has degree $k!$. Now take an arbitrary subset $X$ in $A$ and let $E$ be a set of all edges from $X$, and $E'$ set of all edges from $N(X)$ (the set of all neighbours of vertices in $X$). Then we have $E\subseteq E'$ and so $|E|\leq |E'|$. Now $|E|= (n-k+1)|X|$ and $|E'| = k!|N(X)|$, so we have $$ (n-k+1)|X| \leq k!|N(X)|\implies |X|\leq |N(X)|.$$ By Hall marriage theorem there exists a perfect matching between $A$ and $B$...
...but I can not find one explicitly. Any idea? At least a strategy for $k=3$.