1. [6] Sir Alex is coaching a soccer team of $n$ players of distinct heights. He wants to line them up so that for each player $P$, the total number of players that are either to the left of $P$ and taller than $P$ or to the right of $P$ and shorter than $P$ is even. In terms of $n$, how many possible orders are there?
Answer: $\square$
Solution: We want to determine the number of permutations $\pi$ of $1, \ldots, n$ such that every number is involved in an even number of inversions. The key observation is that the number of inversions $k$ is involved in has the same parity as $\pi(k)-k$. This is since $\pi(k)-k$ can be interpreted as the number of $i$ with $\pi(i)<\pi(k)$ minus the number of $i$ with $i<k$, meaning that $i$ is counted with a weight of $\pm 1 \equiv 1(\bmod 2)$ if and only if $i$ is in an inversion with $k$.
From this, it follows that such permutations are the ones that permute the even and odd numbers, so the answer is $\left\lfloor\frac{n}{2}\right\rfloor!\left\lceil\frac{n}{2}\right\rceil!$.