Problem 1522

Let $t \in\{1,2, \ldots, n\}$. Suppose $a_{t}=t$, then we can choose $i=j=t$ and it follows that $a_{t}+t=n+1$, so $2 t=n+1$. But $n$ is divisible by 4, so $n+1$ is odd. Contradiction. Suppose now that $a_{t}=n+1-t$. Then we can choose $i=n+1-t$ and $j=t$ and it follows that $a_{n+1-t}+t=n+1$, so $a_{n+1-t}=n+1-t$. However, we have just seen that this cannot occur.
Suppose now that $a_{t}=u$ with $u \neq t, u \neq n+1-t$. Then we can choose $i=u$ and $j=t$ and it follows that $a_{u}+t=n+1$, so $a_{u}=n+1-t$. Next, we can choose $i=n+1-t$ and $j=u$ and it follows that $a_{n+1-t}=n+1-u$. Now we choose $i=n+1-u$ and $j=n+1-t$ and see that $a_{n+1-u}=n+1-(n+1-t)=t$. In total, we have:

$$\begin{aligned} a_{t} & =u, \\ a_{u} & =n+1-t, \\ a_{n+1-t} & =n+1-u, \\ a_{n+1-u} & =t . \end{aligned}$$

Since $u \neq t$ and $u \neq n+1-t$, the four numbers on the right-hand side are all different. Furthermore, the four numbers can be divided into two pairs of the form $(v, n+1-v)$. We now have four numbers for which it holds that the same four numbers are in the permutation at the same positions, but in a different order. We can now choose a $t^{\prime}$ different from one of these four numbers and a $u^{\prime}$ with $a_{t^{\prime}}=u^{\prime}$ and find a quartet containing $t^{\prime}$ in the same way. Note that now $n+1-t^{\prime}$ and $n+1-u^{\prime}$ cannot already be in the first quartet, because then $u^{\prime}$ and $t^{\prime}$ would also be in it. We can continue this way until all $n$ numbers are divided into quartets.
We see that we can exactly construct all permutations by applying the following recipe:

- Choose the smallest number $k$ for which $a_{k}$ has not yet been determined. Take $a_{k}=u$ for some $u$ for which $a_{u}$ has not yet been determined and for which $u \neq k, u \neq n+1-k$. This also determines the values of $a_{u}, a_{n+1-u}$ and $a_{n+1-k}$.
- Repeat the previous step as often as necessary until all values $a_{k}$ are determined.

For the first $k$, we have $n-2$ possibilities for $u$. For the next step, we have $n-6$ possibilities. For the step after that, we have $n-10$, and so on. Thus, the number of permutations that satisfy this property is

$$2 \cdot 6 \cdot 10 \cdot \ldots \cdot(n-10) \cdot(n-6) \cdot(n-2)$$

Write $n=4 m$, then we can write this as

$$\begin{gathered} 2^{m} \cdot 1 \cdot 3 \cdot 5 \cdot \ldots \cdot(2 m-5) \cdot(2 m-3) \cdot(2 m-1)=2^{m} \cdot \frac{(2 m)!}{2 \cdot 4 \cdot \ldots \cdot(2 m)} \\ =\frac{(2 m)!}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot m}=\frac{(2 m)!}{m!}=\frac{\left(\frac{1}{2} n\right)!}{\left(\frac{1}{4} n\right)!} \end{gathered}$$