# An illusionist and their assistant are about to perform the following magic trick

Mathematics Asked on January 3, 2022

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 $$Esubseteq 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?

Update: 2020. 12. 20.

NOTE: I found counterexamples to the explicit $$f$$ I initially posted. I removed it but am leaving the rest of the answer up as a partial solution.

## Notation and Remarks

Let $$S_n$$ denote the set of permutations of length $$n$$ and let $$C_{n,k}$$ be the set of covered permutations. For example, the permutation $$12345678 in S_8$$ and $$123cdotcdotcdot78 in C_{8,3}$$. For brevity I often drop the subscripts.

The act of covering gives us a relation $$sim$$ between the two sets, i.e. we say that $$pi in S$$ and $$c in C$$ are compatible if $$c$$ is a covering of $$pi$$. We can visualize this compatibility relation as a bipartite graph. For $$k=2$$ and $$n=3$$ we have:

$$qquad qquad qquad qquad qquad qquad$$

We need to find an injective function $$f : S_n rightarrow C_{n,k}$$ such that $$pi$$ and $$f(pi)$$ are always compatible. The assistant performs the function $$f$$ and the illusionist performs the inverse $$f^{-1}$$. As per the problem requirements, both $$f$$ and $$f^{-1}$$ need to be computable in poly(n) time for a given input. We note that given such an $$f$$, computing $$f^{-1}$$ is straightforward: given a covering $$c$$, we consider the compatible permutations. Among these, we choose the $$pi$$ such that $$f(pi) = c$$.

For $$n = k! + k - 1$$ we note that $$|S_n| = |C_{n,k}| = n!,$$. We also note that each permutation is compatible with exactly $$k!$$ coverings and each covering is compatible with exactly $$k!$$ permutations. As OP mentioned, the Hall marriage theorem thus implies that a solution exists. We can find such a solution using a maximum matching algorithm on the bipartite graph. This is how @orlp found a solution for $$k=3$$ in the comments. However, the maximum matching algorithm computes $$f$$ for every permutation in poly(n!) time, where we instead need to compute $$f$$ for a single permutation in poly(n) time.

Answered by Andrew Szymczak on January 3, 2022

This is a strategy that works in every case I checked, but its validity for all k needs to be proved. By his choice of placing the scarf, the assistant conveys information to the illusionist. There are $$k!$$ ways of placing the scarf, to the assistant.

Consider a random permutation ($$a_1,a_2,...,a_n$$) of {$$1,2,...,n$$}, that the audience chooses. The assistant looks at this arrangement and assigns a parity to it as follows:

1. He takes the $$k$$-touple ($$a_1,a_2,...,a_{k}$$). He constructs a $$k$$-digit number (concatenation) from it as $$a_1a_2...a_{k}$$ He then calculates the rank of this number among all of its $$k!$$ permutations (lowest number gets rank 0 and highest gets rank $$(k!-1)$$). He assigns it a variable $$boxed{x_1=(rank)}$$

2. Assign $$x_2$$ to {$$a_2,a_3,...,a_{k+1}$$}. Similarly assign $$x_3,x_4,...,$$ and $$x_{k!}$$. Take that $$a_i=a_{i+n}$$

Compute the parity: $$p=modleft(sum_{i=1}^{k!} x_i,k!right)$$

There are $$k!$$ values of $$p$$ possible: {$$0,1,2,...,k!-1$$}. Depending on the value of $$p$$ the assistant chooses where to place the scarf. (When $$p=0$$ he places over first $$k!$$ balls. When $$p=1$$ he places over second $$k!$$ balls,.. etc)

When the illusionist sees the obscured arrangement, he knows the value of $$p$$ by the position of the scarf. Although I haven't proved it yet, only one arrangement of the obscured balls gives this value of $$p$$. This strategy works for all cases of $$k=2$$ and many cases of $$k=3$$. But it is a behemoth to prove for general $$(k,n)$$.

Answered by user635640 on January 3, 2022

## Related Questions

### Discussion of continuous functions in topology

2  Asked on December 1, 2021

### Is there a specific name for this geometrical shape?

1  Asked on December 1, 2021

### Are regular/Riemann integrals a special case of a line integral?

2  Asked on December 1, 2021 by pendronator

### Injection from $(Kotimes_{mathbb{Z}}hat{mathbb{Z}})^*to prod_p(Kotimes_{mathbb{Z}}mathbb{Z}_p)^*$?

1  Asked on December 1, 2021

### Classification of triply transitive finite groups

1  Asked on December 1, 2021 by jack-schmidt

### Lebesgue Measure Space and a converging, increasing sequence. Show that the sequence in increasing.

1  Asked on December 1, 2021 by martinhynesone

### What is the derivative of $log det X$ when $X$ is symmetric?

3  Asked on December 1, 2021 by evangelos

### Uncertainty of a Weighted Mean with Uncertain Weights

1  Asked on December 1, 2021 by alex-howard

### The Grothendieck-Serre Correspondence : Obstructions to the construction of the cyclic group of order 8 as a Galois group?

1  Asked on December 1, 2021

### Prove/disprove that $mathbb{R}^2 /$~ is hausdorff, when: $(x_1,x_2)$~$(y_1,y_2)$ if there is $t>0$ such that $x_2 = tx_1$ and $ty_2 = y_1$

1  Asked on December 1, 2021 by gabi-g

### Definition of ring of dual numbers

1  Asked on December 1, 2021 by ponchan

### Are chain complexes chain equivalent to free ones?

1  Asked on December 1, 2021

### all prime numbers except 2 can write in the form $4npm1$

4  Asked on December 1, 2021 by aligator

### Time Average Mean of X(t)=A, where A is a r.v. Ergodic vs. non-ergodic.

1  Asked on December 1, 2021

### The complexity of finiteness

1  Asked on December 1, 2021

### Question about step in Ahlfors’ proof of Cauchy’s inequality in complex analysis.

1  Asked on December 1, 2021

### Numerical differentation – finding maxima

0  Asked on December 1, 2021

### Neyman–Pearson Lemma

1  Asked on December 1, 2021 by noe-vidales

### Is the determinant a tensor?

1  Asked on December 1, 2021