Iranian Mathematical Olympiad

We shall prove that the answer is $2^{\lfloor \frac{n}{2} \rfloor}$. We shall firstly prove the following lemma;

Lemma 1. Let $i = 2^{\nu_2(i)}m$, $\gcd(2, m) = 1$ then $a_i = 2^j m$ for some $j \in \{0, 1, \dots, 1+\nu_2(i)\}$.

Proof. We shall prove this statement through induction on $m$. Notice that for $m=1$ and for $i \in \{2^j \mid 2^j \le n, j \in \{0, 1, \dots\}\}$, the number $a_i$ would also be an element of that set. Hence, $a_i$ would be a permutation of $\{2^j \mid 2^j \le n, j \in \{0, 1, \dots\}\}$

Now, let for all odd $N > m$ such, if $i \in \{2^j N \mid 2^j N \le n, j \in \{0, 1, \dots\}\}$ then $a_i$ must be a permutation of the same set. Setting $i = 2^{\nu_2(i)}m$ and $a_i = 2^j N$ such that $N \mid m$ and $j \le 1 + \nu_2(i)$. Since we have already used all the numbers with the odd parts less than $m$ we find that $N = m$ and we are done.

We shall now claim that after the determination of all number of the form $a_k = 2k$, $k = 1, 2, \dots, \lfloor \frac{n}{2} \rfloor$ the permutation would indeed uniquely be determined. According to the above lemma, it only suffices to restrict ourselves to the set $\{2^j m : 2^j m \le n, j = 0, 1, \dots\}$. We draw a directed graph having $n$ vertices that are collinear, such that the in- and out- degree of each vertex is 1 and from each vertex the out edge would either go to the next vertex or to one of the vertices before hand. Now, if we determine those vertices with the edge to the next, we can uniquely determine the other edges. For this reason, we shall prove the following lemma;

Lemma 2. *If the $k$-th vertex be the first with zero out-degree, then no edge would go out of the set of vertices $\{1, 2, \dots, k\}$. Moreover, there is only one vertex with the zero in-degree.*

Proof. Since any edge that is out from $\{1, 2, \dots, k-1\}$ will go some vertex in the set $\{1, 2, \dots, k\}$ and the $k$ has the out-degree to its left (otherwise its out-edge has yet been determined!). The first part of the lemma would be obvious. For the second part, regard that the sum of in-degrees and out-degrees would be equal. This completes our proof.

Thus, at each step that we face the first vertex with zero out-degree, we connect it to the previous vertex with the zero in-degree and continue this procedure. Since for each of $1, 2, \dots, \lfloor \frac{n}{2} \rfloor$ we have two choices, the final answer would be $2^{\lfloor \frac{n}{2} \rfloor}$, as desired.