KöMaL 2025 A913

Let $n$ be a positive integer. Marci writes down the first $n$ positive integers in some order in his notebook, which we cannot see. Let this order be $m(1),m(2),\ldots,m(n)$; we would like to determine this order. In one step we may also list the first $n$ positive integers for Marci in some order, let this be $a(1),\ldots,a(n)$. Then Marci, in his notebook (which we cannot see), draws a directed graph on $n$ vertices, labelled with $1,2,\ldots,n$, respectively. After this, for every integer $1\leq i\leq n$, he draws a directed edge from the vertex labelled $i$ to the vertex labelled $m(a(i))$. Finally, the resulting graph with $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 $n\log_2(n)$ steps. b) Does there exist a constant $c<1$ such that for every positive integer $n$ the secret permutation can be determined in at most $cn\log_2(n)$ steps?