For any permutation $\sigma$ of $\{ 1, \dots ,n \}$ there exists $k$ such that $|k- \sigma (k)| \le \frac{n}{2}$

Question

Let $n \ge 2$ be an even number. Is the following true?

For any permutation $\sigma$ of $\{ 1, \dots ,n \}$ there exists $k$ such that $$|k- \sigma (k)| \le \frac{n}{2}$$

and is $n/2$ optimal? I mean, is it true that $$\max_{\sigma \in S_n} ( \min_{1 \le k \le n} |k- \sigma (k)| ) = \frac{n}{2}$$

Considering the permutation $$\sigma^*_n(k) = \begin{cases}k + \frac{n}{2} & \ \mathrm{if} \ k \le \frac{n}{2} \\ k - \frac{n}{2} & \ \mathrm{if} \ k > \frac{n}{2}\end{cases}$$ every element of $\{ 1, \dots ,n\}$ is mapped to something disting at least $n/2$. This shows that $$\max_{\sigma \in S_n} ( \min_{1 \le k \le n} |k- \sigma (k)| ) \ge \min_{1 \le k \le n} |k- \sigma^*_n (k)| =\frac{n}{2}$$ Can we do better or is this the best case?

Answer 1

You cannot do better; for any even $n$ you have $$\left|\tfrac n2-\sigma(\tfrac n2)\right|\leq\tfrac{n}{2}.$$

Answer 2

It is optimal and we can take $k = \frac{n}{2}$: as $1 \leqslant \sigma(k) \leqslant n$, we have $1 - \frac{n}{2} \leqslant \sigma(\frac{n}{2}) - \frac{n}{2} \leqslant \frac{n}{2}$, thus $|\frac{n}{2} - \sigma(\frac{n}{2})| \leqslant \frac{n}{2}$.