Problem A. 913. (September 2025)

A. 913. Let $\displaystyle n$ be a positive integer. Marci writes down the first $\displaystyle n$ positive integers in some order in his notebook, which we cannot see. Let this order be $\displaystyle m(1),m(2),\ldots,m(n)$; we would like to determine this order. In one step we may also list the first $\displaystyle n$ positive integers for Marci in some order, let this be $\displaystyle a(1),\ldots,a(n)$. Then Marci, in his notebook (which we cannot see), draws a directed graph on $\displaystyle n$ vertices, labelled with $\displaystyle 1,2,\ldots,n$, respectively. After this, for every integer $\displaystyle 1\leq i\leq n$, he draws a directed edge from the vertex labelled $\displaystyle i$ to the vertex labelled $\displaystyle m(a(i))$. Finally, the resulting graph with $\displaystyle n$ edges decomposes into a disjoint union of directed cycles (each of which may consist of a single loop), and Marci tells us the number of these cycles.

a) Prove that the secret permutation can be determined in at most $\displaystyle n\log_2(n)$ steps.

b) Does there exist a constant $\displaystyle c<1$ such that for every positive integer $\displaystyle n$ the secret permutation can be determined in at most $\displaystyle cn\log_2(n)$ steps?

Proposed by: Márton Németh, Budapest

(7 pont)

Deadline expired on October 10, 2025.

For the sake of cleaner notation, we shall interpret the problem as follows: there is a secret $\displaystyle \sigma\in S_n$ permutation. In a question, we may specify a permutation $\displaystyle \pi\in S_n$, and we're told the number of cycles in permutation $\displaystyle \sigma\circ\pi$.

We seek to find a permutation $\displaystyle \pi$ for which $\displaystyle \sigma\circ\pi = \mathrm{id}$, that is, the number of cycles is $\displaystyle n$. We're then done, since this would imply $\displaystyle \sigma = \pi^{-1}$. We need some tools first.

1. lemma: Assume we know $\displaystyle x_1$, $\displaystyle x_2$, $\displaystyle \ldots$, $\displaystyle x_k$ are in disjoint cycles in $\displaystyle \sigma$, and we know the cycle count of $\displaystyle \sigma$. Then one question is enough to decide whether $\displaystyle y\neq x_i$ is in the same cycle as one of the $\displaystyle x_i$ or not.

Proof: Let $\displaystyle \pi = (y\, x_1\, x_2\, \ldots\, x_k)$. There's two cases:

If $\displaystyle y$ doesn't share a cycle with any of the $\displaystyle x_i$, then it's in a $\displaystyle k+1$-th cycle, so

$\displaystyle \sigma = (x_1\, x_{1,2}\, x_{1,3}, \ldots)(x_2\, x_{2,2}\, x_{2,3}\, \ldots)\ldots (y\, y_2\, y_3\, \ldots)\tau, $

where $\displaystyle \tau$ denotes disjoint cycles with the ones in question. Then

$\displaystyle \sigma\circ \pi = (x_{1,2}\, \ldots, x_1\, x_{2,2}\,\ldots\,x_2\,x_{3,2}\,\ldots\, y)\tau $

so the number of cycles decreased by $\displaystyle k$. If on the other hand $\displaystyle y$ is in the same cycle as one of the $\displaystyle x_i$, we assume WLOG, it's $\displaystyle x_1$, so

$\displaystyle \sigma = (x_1\, x_{1,2}\, \ldots\, x_{1,l-1}\, y\, x_{1,l+1}\,\ldots)(x_2\, x_{2,2}\, x_{2,3}\, \ldots)\ldots(x_k\, x_{k,2}\, x_{k,3}\, \ldots)\tau. $

Since

$\displaystyle \sigma\circ\pi = (x_{1,l+1}\, \ldots\, x_1\, x_{2,2}\,\ldots x_k)(y\, x_{1,2}\, x_{1,3}\, \ldots\, x_{1,l-1})\tau, $

$\displaystyle k$ cycles got replaced by $\displaystyle 2$ outside of $\displaystyle \tau$. These cases are distinguishable.

2. lemma: Assume we know $\displaystyle x_1$, $\displaystyle x_2$, $\displaystyle \ldots$, $\displaystyle x_k$ are in pairwise disjoint cycles in $\displaystyle \sigma$, and we know the cycle count of $\displaystyle \sigma$. Then we can select which $\displaystyle x_i$ the value $\displaystyle y\neq x_i$ shares a cycle with (from $\displaystyle k$ of them), or conclude none of them, with at most $\displaystyle \lceil \log_2(k+1)\rceil$ questions.

Proof: This is a simple binary search using the first lemma: There's $\displaystyle k+1$ possibilities, and we may halve the number of possibilities with each question.

We now present the full algorithm: first ask for $\displaystyle \pi = \mathrm{id}$, so we know the number of cycles in $\displaystyle \sigma$ to begin with. We do $\displaystyle n$ steps. By the end of the $\displaystyle i$th step, we want to have a permutation $\displaystyle \pi_i$, for which it holds, that in $\displaystyle \sigma\circ \pi_i$, the values $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i$ are in pairwise disjoint cycles, and we know the cycle count of $\displaystyle \sigma\circ\pi_i$. The first step ($\displaystyle i=1$) is easy: $\displaystyle \pi_1 = \mathrm{id}$ suffices.

Assume by induction that thee first $\displaystyle i-1$ steps have been completed. With the second lemma, we conclude which $\displaystyle 1\leq j\leq i-1$ shares a cycle with $\displaystyle i$ in $\displaystyle \sigma\circ\pi_{i-1}$, or none at all. In the latter case, $\displaystyle \pi_i=\pi_{i-1}$ suffices.

If $\displaystyle j$ shares its cycle with $\displaystyle i$, then let $\displaystyle \pi_i = \pi_{i-1}(i\, j)$. As seen in the proof of the first lemma, this splits the cycle in two. Since we knew the cycle count of $\displaystyle \sigma\circ \pi_{i-1}$, we know it for $\displaystyle \sigma\circ \pi_{i}$ as well, without wasting a question.

After $\displaystyle n$ steps, we acquire $\displaystyle \pi = \pi_n$-t, which satisfies the goal from the beginning ($\displaystyle \sigma\circ \pi_n$ has $\displaystyle n$ cycles), so we're done. We now calculate the number of questions used:

The $\displaystyle i$th step uses at most $\displaystyle \lceil \log_2(i)\rceil$ questions, and we started by asking for $\displaystyle \pi=\mathrm{id}$.

$$\begin{align*} 1+\sum_{i=1}^{n} \lceil \log_2(i)\rceil &\leq 1+\int_1^{n} \log_2(x)\mathrm{d}x +\log_2(n)+1\\ &= 2 + \frac{1}{\log(2)} \int_1^{n} \log(x)\mathrm{d}x + \log_2(n)\\ &= 2 + \frac{\left [ x\log x - x \right ]_1^{n}}{\log(2)} + \log_2(n)\\ &= 2 + \frac{n\log(n) - n + 1}{\log(2)} + \log_2(n) \\ &= n\log_2(n) - 1 + \left [3 + \frac{1}{\log(2)} + \log_2(n) - \frac{n}{\log(2)} \right ]. \end{align*}$$

It's easy to check that for $\displaystyle n\geq 5$, the expression in brackets is negative. For $\displaystyle n=2$, $\displaystyle 1$ question is enough, for $\displaystyle n=3$, we use at most $\displaystyle 1$ question in the third step, so $\displaystyle 3$ questions are enough, for $\displaystyle n=4$, the right hand side is $\displaystyle 1+0+1+2+2=6$, so $\displaystyle n\log_2(n) - 1$ questions are always enough.

For part b)we need some extra tricks. We aim to handle $\displaystyle 2$ values at the same time instead of just one.

Assume we know, that in $\displaystyle \sigma \circ \pi_{i-2}$ (where $\displaystyle i\geq 3$) the values $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i-2$ are in pairwise disjoint cycles, and we know the cycle count of $\displaystyle \sigma\circ \pi_{i-2}$. We construct a permutation $\displaystyle \pi_i$, for which in $\displaystyle \sigma\circ\pi_i$ the values $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i$ are in disjoint cycles.

First ask for the cycle count of $\displaystyle \sigma\circ\pi_{i-2}\circ (i-1\, i)$, we'll then know whether $\displaystyle i$ and $\displaystyle i-1$ are in the same cycle or not. If so, it's easy: as per the second lemma, we determine which $\displaystyle j<i-1$ the value $\displaystyle i-1$ shares a cycle with (ot none of them), and split it off. In the new permutation, $\displaystyle i$ can only share a cycle with $\displaystyle i-1$ or the determined $\displaystyle j$ (if such exists), so we test for that using one more question. We used at most

$\displaystyle \left \lceil \log_2(i-1) \right \rceil + 2 $

questions, and acquired permutation $\displaystyle \pi_i$ as a product of $\displaystyle \pi_{i-2}$ and $\displaystyle 0$, $\displaystyle 1$ or $\displaystyle 2$ transpositions.

We now make sure that $\displaystyle i-1$ and $\displaystyle i$ are in the same cycle as some $\displaystyle j_{i-1} < i-1$ and $\displaystyle j_i < i-1$ (we already know $\displaystyle j_{i-1} \neq j_i$). This uses two questions (we combine $\displaystyle i$ and $\displaystyle i-1$ with the smaller values separately). If either $\displaystyle i$ or $\displaystyle i-1$ doesn't share a cycle with a smaller value, we again need only

$\displaystyle \left \lceil \log_2(i-1) \right \rceil + 3 $

questions.

We're done with the easy cases (they can actually be omitted, we did them to avoid analysing cases in the main algorythm). We proceed by describing two phases:

Phase $\displaystyle A$: we do not yet have two disjoint sets $\displaystyle Y, Z\subset \{1, 2, \ldots, i-2\}$, for which we know that $\displaystyle j_{i-1}\in Y$ and $\displaystyle j_i\in Z$. But we do have a set $\displaystyle X\subset \{1, 2, \ldots, i-2\}$, for which $\displaystyle j_{i-1}, j_i\in X$. At the beginning of the phase, $\displaystyle X = \{1, 2, \ldots i-2\}$ suffices.

We first ask two questions to find a set $\displaystyle X'\subset X$, for which

$\displaystyle \left \lceil \frac{|X|}{4} \right\rceil \geq |X'| \geq \left \lfloor \frac{|X|}{4} \right\rfloor $

and $\displaystyle j_{i-1}\in X'$. We now ask just one question to determine whether $\displaystyle j_i$ is in $\displaystyle X'$ or not. If so, then $\displaystyle 3$ questions were enough to roughly quarter the size of $\displaystyle X$, we restart phase $\displaystyle A$ with $\displaystyle X'$.

If instead $\displaystyle j_i\notin X'$, then we found suitable sets $\displaystyle Y$, $\displaystyle Z$ as described. Before we enter phase $\displaystyle B$ we clear them up a bit: let $\displaystyle Y=X'$, and with two question, narrow possibilities for $\displaystyle j_i$ to a set $\displaystyle Z\subset X\setminus X'$ with $\displaystyle |Z| = |Y|$.

Phase $\displaystyle B$: we already have sets $\displaystyle Y$, $\displaystyle Z$ as described. We aim to use $\displaystyle 3$ questions to decrease the size of both $\displaystyle Y$ and $\displaystyle Z$ by a factor of $\displaystyle 3$. Let $\displaystyle Y=Y_1\cup Y_2\cup Y_3$ és $\displaystyle Z=Z_1\cup Z_2\cup Z_3$, where the partitions are pairwise disjoint, and their sizes pairwise differ by at most $\displaystyle 1$. Let $\displaystyle Y_1 = \{y_1, y_2, \ldots, y_k\}$ and $\displaystyle Z_1 = \{z_1, z_2, \ldots, z_l\}$.

Ask for the cycle count of $\displaystyle \sigma\circ\pi_{i-2}\circ (y_1\, \ldots\, y_k\, i-1)\circ (z_1\, z_2\, \ldots\, z_l\, i)$.

If $\displaystyle j_{i-1}\in Y_1$, $\displaystyle j_i\in Z_1$, then the number of cycles changed by $\displaystyle -k-l+2+2$.
If $\displaystyle j_{i-1}\in Y_1$, $\displaystyle j_i\notin Z_1$, or the other way around, the number of cycles changed by $\displaystyle -k-l-1+2+1$.
If $\displaystyle j_{i-1}\notin Y_1$, $\displaystyle j_i\in Z_1$, then the number of cycles changed by $\displaystyle -k-1-l-1+1+1$.

It's apparant, that these cases are well distinguishable. In the first case this $\displaystyle 1$ question was enough to achieve our goal, $\displaystyle Z_1$ and $\displaystyle Y_1$ suffice, and we restart phase $\displaystyle B$.

In the third case $\displaystyle j_{i-1}\in Y_2\cup Y_3$ és $\displaystyle j_{i}\in Z_2\cup Z_3$, So we halve both sets with $\displaystyle 2$ more questions.

In the second case, we use one question to decide whether $\displaystyle j_{i-1}\in Y_1$ or $\displaystyle j_i\in Z_1$ is the case, and we use one more question to halve the set nessecary.

For some constant $\displaystyle c_1$, we always use at most

$\displaystyle 3\log_3(i-2) + c_1 $

questions to acquire permutation $\displaystyle \pi_i$ (phase $\displaystyle A$ is cheaper then phase $\displaystyle B$).

So for some constant $\displaystyle c_2$ we always need at most

$\displaystyle \dfrac{n}{2}\cdot 3\log_3(n) + c_2n = \dfrac{3\log_3(2)}{2}n\log_2(n) + c_2n$

questions. Let

$\displaystyle \dfrac{3\log_3(2)}{2} < c_3 < 1, $

and $\displaystyle K$ some boundary index, for which whenever $\displaystyle n\geq K$,

$\displaystyle \dfrac{3\log_3(2)}{2}n\log_2(n) + c_2n \leq c_3n\log_2(n). $

Finally, as seen in part $\displaystyle a)$, for all $\displaystyle n$ we need at most $\displaystyle n\log_2(n) - 1$ questions, so let $\displaystyle c_4 < 1$ be such that for all $\displaystyle n<K$

$\displaystyle c_4n\log_2(n) \leq n\log_2(n) - 1. $

Then $\displaystyle c = \max (c_3, c_4) < 1$ meets the criteria of the problem.

Statistics:

10 students sent a solution.

5 points: 1 student.

4 points: 3 students.

1 point: 2 students.

0 point: 2 students.

Unfair, not evaluated: 2 solutionss.

Problems in Mathematics of KöMaL, September 2025

10 students sent a solution.
5 points:	1 student.
4 points:	3 students.
1 point:	2 students.
0 point:	2 students.
Unfair, not evaluated:	2 solutionss.

Already signed up?
New to KöMaL?