A friend send me this exercise. I haven't be able to solve it since, except finding particular cases for $n=2$ or $n=3$. What would be your starting point ?
Can we find the optimal $\sigma$ ? And can we compute the value of the sum for such a $\sigma$ ?
$$\min_{\sigma\in\mathfrak{S}_n}\sum_{i=1}^n\left\lfloor\frac{\sigma(i)}{i}\right\rfloor$$
Where $\mathfrak{S}_n$ denotes the permutations set.