The idea of the solution is fine but it should be $a_{n+1}=a_n([n/2]+1)$.

Sorry, yeah. I wrote that in my paper, just forgot to add it here

Good problem. If $n=2k$, $\boxed{M_n=(k!)^2}$; If $n=2k+1$, $\boxed{M_n=(k!)^2\cdot(k+1)}$.

I don't know how to explain this but let's go Let $a_n$ the number of magical permuntations of $\{1, 2, ..., n\}$ and $P_n$ the n-th position of a set. (For example, in the set $\{2, 3, 1\}$ the number at $P_2$ is 3, we say $k \in \{P_i, P_j\}$ if $k$ can be the $i$-th or $j$-th position of a set) Take $\{b_1, b_2, ..., b_n\}$ a magical permutation of $\{1, 2, ..., n\}$ and $b_{n+1} = n + 1$ We know $\left\lfloor \frac{b_{n+1}}{2} \right\rfloor$ $\in \{P_{\lfloor \frac{n+1}{2} \rfloor + 1}, ..., P_{n+1}\}$ so when we put $b_{n+1}$ in the set all the new sets are magic, then $a_{n+1} = (n + 1 - \left \lfloor \frac{n + 1}{2} \right \rfloor)a_n$ if $n = 2k$ $\Longrightarrow a_n = k . a_{2k-1}$ if $n = 2k + 1$ ($n > 1$) $\Longrightarrow a_n = (k + 1)a_{2k}$ $\therefore a_n = \begin{cases} (k!)^2, n = 2k \\ (k!)^2\cdot(k + 1), n = 2k + 1 \end{cases}$

Solution without recurrence: 1)Let $a_1 , a_2 , ... , a_n$ a magical permutation of $1, 2, 3, ... , n , n>1$ Note that $a_i < 2 * (i)$, because $a_i$ just has $i-1$ numbers on his left. $1 \le i \le \left \lfloor \frac{n}{2}\right \rfloor$ 2)If $a_1 , a_2 , ... , a_n$ is a permutation of $1, 2, 3, ... , n , n>1$ such that $a_i < 2 * (i)$ , $1 \le i \le \left \lfloor \frac{n}{2} \right \rfloor$, we have that for $1 \le j \le n$ , $j \le n \Rightarrow \left \lfloor \frac{j}{2} \right \rfloor \le \left \lfloor \frac{n}{2} \right \rfloor$, so $a_1, a_2, .... , a_{\left \lfloor \frac{j}{2} \right \rfloor}$ are less than $2 * \left \lfloor \frac{j}{2} \right \rfloor \le j$. Therefore, $a_1 , ... , a_n$ is a magical permutation. 2.5) 1 and 2 tell us that $a_1 , a_2 , ... , a_n$ is a magical permutation of $1, 2, 3, ... , n$ if and only if $a_i < 2 * (i)$ , $1 \le i \le \left \lfloor \frac{n}{2} \right \rfloor$ 3)Now, let's find the number of permutations that $a_i < 2 * (i)$ , $1 \le i \le \left \lfloor \frac{n}{2} \right \rfloor$ $a_1 < 2 * (1)$ has $1$ possibility (1) $a_2 < 2 * (2)$ has $3-1$ possibilities (2, 3) (the $1$ has been chosen by $a_1$) $a_3 < 2 * (3)$ has $5-2=3$ possibilities $a_4 < 2 * (4)$ has $7-3=4$ possibilities ... $a_i < 2 * (i)$ has $(2 * (i) -1) - (i-1) = i$ possibilities, because $a_1, a_2, ..., a_{i-1}$ selected $i-1$ numbers of $1, 2, ..., 2 * (i)$ ... $a_{\left \lfloor \frac{n}{2} \right \rfloor} < 2 * \left \lfloor \frac{n}{2} \right \rfloor $ has $2 * \left \lfloor \frac{n}{2} \right \rfloor -1 - \left (\lfloor \frac{n}{2} \right \rfloor - 1) = \left \lfloor \frac{n}{2} \right \rfloor$ possibilities. There are $1 * 2 * 3 * 4 * ... * \left \lfloor \frac{n}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor!$ possibilities. Now, for the numbers $a_{\left \lfloor \frac{n}{2} \right \rfloor + 1} , a_{\left \lfloor \frac{n}{2} \right \rfloor + 2} , ... , a_n$, they are a permutation of the $n - \left \lfloor \frac{n}{2} \right \rfloor$ numbers that we didn't use. There are $(n - \left \lfloor \frac{n}{2} \right \rfloor)!$ possibilities. 4) Finally, the total permutations are: $\left \lfloor \frac{n}{2} \right \rfloor! * (n - \left \lfloor \frac{n}{2} \right \rfloor)!$ Using 2.5, these are the total number of magical permutations. For n=1 is trivial

This problem was proposed by Gerardo Fisch from Paraguay