A pretty good exercise for training technical habits at home, but definitely not nice for doing it under pressure at IMO, it's good it was not selected. Denote the required minimum by $f(n)$. Suppose $a_k = n$ where $k<n$. Then we may assume $a_{n} = n - 1$ -- otherwise by swapping $a_n$ and $n-1$ the sum will not increase, as $a_n < n-1$ imply $\left\lfloor \frac{n-1}{j} \right\rfloor \geq \left\lfloor \frac{a_n}{j} \right\rfloor$ and $\left\lfloor \frac{a_n}{n} \right\rfloor = \left\lfloor \frac{n-1}{n} \right\rfloor = 0$. Analogously we may assume $a_{n-1} = n - 2$, $a_{n-2} = n-3$ and so on up to $a_{k+1} = k$. Now if $k\geq 2$, then $a_1, \ldots, a_{k-1}$ are a permutation of $1,2,\ldots,k-1$, so overall we have $f(n) = \min_{1\leq k \leq n} \left[f(k-1) + \left\lfloor \frac{n}{k} \right\rfloor\right]$ (conventionally treating $f(0) = 0$). To deal with this painful recurrence, calculate up to e.g. $f(10)$ (or $f(20\mbox{-ish})$ if you have time and nerves) in order to suspect $f(n) = 1 +\lfloor \log_2 n \rfloor$ which we shall prove by induction! The case $n=1$ is immediate. For the induction step we have to show $\lfloor\log_2(k-1)\rfloor + \left\lfloor \frac{n}{k} \right\rfloor \geq \lfloor \log_2 n \rfloor$ for all $k=2,3,\ldots,n$ and that equality is attained (we omitted $k=1$ since then the recurrence yields $n \geq 1 + \log_2 n$). Write $n = 2^s + \ell_1$ and $k = 2^t + \ell_2$ where $0\leq \ell_1 < 2^s$, $1\leq \ell_2 \leq 2^t$ and observe that $s\geq t$ since $s\leq t-1$ and $n\geq k$ would imply $2^t - 1 \geq 2^{s+1} - 1 \geq 2^s + \ell_1 \geq 2^t + \ell_2 \geq 2^t + 1$, contradiction! The inequality becomes $\left\lfloor \frac{2^s + \ell_1}{2^t + \ell_2}\right\rfloor \geq s-t$. The left hand side is minimal for $\ell_1$ minimal and $\ell_2$ maximal, so we reduce to $2^{s-t-1} \geq s-t$, which is true since $s\geq t$ and $2^{m-1} \geq m$ holds for all $m\geq 1$ by a trivial induction (and clearly for $m=0$ as well). Equality holds e.g. for $t=s-1$ and $\ell_2 = \left\lceil \frac{\ell_1+1}{2} \right\rceil$ (note that this value for $\ell_2$ is indeed in $[1,2^{s-1}]$).

The answer is $1+\lfloor \log_2(n) \rfloor$. We first bound, then give a construction. Claim: there exists a permutation with $S(\pi)$ minimal, such that $\lfloor \frac{\pi(j)}{j} \rfloor < 2$ for all $1\le j\le n$ Proof: We first deal with $j=1$. Suppose otherwise $\pi(1)\ne 1$, then there exists $m>1$ such that $\pi(m)=1$. Swap $\pi(1),\pi(m)$ then the change in the sum is $$1+\left \lfloor \frac{\pi(1)}{m} \right\rfloor - \pi(1) \le 0$$ Now assume $j\ge 2$. Suppose $m\ge 2$ and $mj\le \pi(j) < (m+1)j$, then we pick $k$ such that $$k \ge \frac{(m+1)j}{2} \text{ and } \pi(k)<mj$$ This $k$ exists because there are $mj-1$ values of $k$ such that $\pi(k)<mj$. The largest of them is at least $mj-1\ge \frac{(m+1)j}{2}$ as $m,j\ge 2$. We swap $\pi(j), \pi(k)$. The difference is $$\left\lfloor \frac{\pi(j)}{k} \right\rfloor + \left \lfloor \frac{\pi(k)}{j} \right\rfloor - \left \lfloor \frac{\pi(j)}{j} \right\rfloor - \left \lfloor \frac{\pi(k)}{k} \right\rfloor \le 1+(m-1)-m = 0 $$ After swapping, $$T(\pi)=\sum\limits_{j \text{ st } \pi(j)\ge 2j} \pi(j)$$ Strictly decreases since I've dropped $\pi(j)$ and may or may not have added a smaller term $\pi(k)$. Now, let $S=\{j | \pi(j)\ge j\}$, then the answer is merely $|S|$. Let $S=\{s_1<s_2<\cdots\}$ Claim: $s_j\le 1+s_1+\cdots+s_{j-1}$ Proof: Let $g(j)=\pi(1)+\cdots+\pi(j) - (1+\cdots+j)$. It's clear that $g(j)\ge 0$ for all $1\le j\le n$. On the other hand, $$g(j)=\sum\limits_{k=1}^j (\pi(k)-k) \le \sum\limits_{k\in S, k\le j} (2k-1-k) + \sum\limits_{k\in \{1,\cdots,j\}\backslash S} (-1) = \left(\sum\limits_{k\in S} k\right) - j$$ Therefore, if $s_j>1+s_1+\cdots+s_{j-1}$, then $$0\le g(1+s_1+\cdots+s_{j-1})\le s_1+\cdots+s_{j-1} - (1+s_1+\cdots+s_{j-1})=-1$$ Absurd! This in turn implies $s_j\le 2^{j-1}$.

Answer as pointed before. Very rough sketch below because I can't bother to type the whole thing out.

The answer is $\left\lfloor \log_2 n \right\rfloor + 1$. Letting $f(n)$ denote the answer, we prove this by induction on $n \ge 1$. The base cases $n=1$ and $n=2$ are easy. For $n \ge 3$, consider a permutation $(a_i)_i$ with minimal sum and let $t$ denote the position of $n$, meaning we have an expression \[ f(n) = \dots + \left\lfloor \frac{\bullet}{t-1} \right\rfloor + \left\lfloor \frac nt \right\rfloor + \left\lfloor \frac{\bullet}{t+1} \right\rfloor + \dots + \left\lfloor \frac{\bullet}{n-1} \right\rfloor + \left\lfloor \frac{\bullet}{n} \right\rfloor. \]Then we can make the following $n-t$ transformations without increasing the value of the right-hand side: Swap $n-1$ into the $n$th floor (i.e.\ the last term) Swap $n-2$ into the $(n-1)$st floor (i.e.\ the second-to-last term) \dots Swap $t$ into the $(t+1)$st floor (i.e.\ the term after $\left\lfloor n/t \right\rfloor$). After these swaps, we get \begin{align*} f(n) &= f(t-1) + \left\lfloor \frac nt \right\rfloor + 0 + \dots + 0\\ &= \left\lfloor \log_2(t-1) \right\rfloor + 1 + \left\lfloor \frac nt \right\rfloor. \end{align*}So we just need the value of $t$ that minimizes the right-hand side. This is split into two cases: If $n/2 < t \le n$, we have \[ f(n) \ge \left\lfloor \log_2 \left( \left\lceil \frac{n+1}{2} \right\rceil - 1 \right) \right\rfloor + 2 = \left\lfloor \log_2 n \right\rfloor + 1 \]with equality if $t = \left\lceil (n+1)/2 \right\rceil$. If $t \le n/2$, then we do an extremely annoying calculation to prove \[ \left\lfloor \log_2(t-1) \right\rfloor + \left\lfloor \frac nt \right\rfloor \ge \left\lfloor \log_2 n \right\rfloor \qquad (\diamondsuit). \]We will twice use the fact that $\alpha \ge \log_2 \alpha + 1$ for all $\alpha \ge 2$, which we denote $(\spadesuit)$. If $t$ is not a power of $2$, then $\left\lfloor \log_2(t-1) \right\rfloor = \left\lfloor \log_2 t \right\rfloor$ and \begin{align*} (\diamondsuit) \iff \left\lfloor \frac nt \right\rfloor &\overset{?}{\ge} \left\lfloor \log_2 n \right\rfloor - \left\lfloor \log_2 t \right\rfloor \\ \Longleftarrow \left\lfloor \frac nt \right\rfloor &\overset{?}{\ge} \left\lfloor \log_2 \frac{n}{t} \right\rfloor + 1 \\ \Longleftarrow \frac nt &\overset{?}{\ge} \log_2 \frac{n}{t} + 1 \Longleftarrow (\spadesuit). \end{align*}If we are unlucky and $t = 2^e$, then instead let $n = 2^e q + r$, with $0 \le r < 2^e$ and $q \ge 2$. The main insight is that $\left\lfloor \log_2 (2^e q + r) \right\rfloor = \left\lfloor \log_2 (2^e q) \right\rfloor$, so \[ (\diamondsuit) \iff (e-1) + q \ge \left\lfloor \log_2(2^eq + r) \right\rfloor = \left\lfloor \log_2(2^e q) \right\rfloor = e + \left\lfloor \log_2 q \right\rfloor. \]Thus it suffices to show $q \ge \log_2 q + 1$ which is $(\spadesuit)$.

The answer is $\lfloor \log_2(n) \rfloor+1$. Let $k$ be such that $2^k \leq n <2^{k+1}$. We want to prove that the given sum is $\geq k+1$. The key Claim is the following: Claim: $\lfloor \frac{x}{y} \rfloor \geq \log_2(\frac{x+1}{y})$ Proof: Note that $y2^{\lfloor \frac{x}{y} \rfloor}>y2^{x/y-1} \geq y(x/y-1+1)=x,$ and so $y \cdot 2^{\lfloor \frac{x}{y} \rfloor} \geq x+1$, which easily rearranges to what we wanted to prove $\blacksquare$ Thus, $ \sum_{i=1}^{n} \lfloor \frac{a_i}{i} \rfloor \geq \log_2(\frac{\displaystyle \prod(a_i+1)}{n!})=\log_2(n+1)>\log_2(n) \geq k,$ and so $\sum_{i=1}^{n} \lfloor \frac{a_i}{i} \rfloor \geq k+1$, since both sides are integers. Now, in order to prove that this value can be achieved, consider the following permutation: $a_1=1$ $a_2=2, a_3=2$ $a_4=7,a_5=4,a_6=5,a_7=6,$ and in general $a_{2^i}=2^{i+1}-i,a_{2^i+1}=2^i,\ldots,a_{2^{i+1}-1}=2^{i+1}-2$. The last 2 groups are $2^k-1,2^{k-1},\ldots,2^k-2$ and $n,2^k,2^k+1,\ldots,n-1$ It is easy to check that we have $k+1$ groups in total and in each group, the sum of the floors is equal to $1$, so in total the sum is equal to $k+1$, as we wanted.

ISL 2021 A3. Given a positive integer $n$, find the smallest value of $\sum\limits_{k=1}^n\left\lfloor\frac{a_k}k\right\rfloor$ over all permutations $(a_1, \dots, a_n)$ of $(1, \dots, n)$. Solution. Let \[\{\vec a=(a_1, \dots, a_n)\}=S_n\subseteq\mathbb R^n\]be the set of all permutations of $(1, \dots, n)$. (Technically, the set of all images of all permutations.) Let \[f_n(\vec a)=\sum\limits_{i=1}^n\left\lfloor\frac{a_i}i\right\rfloor\]and \[g(n)=\min\limits_{\vec a\in S_n}f_n(\vec a).\]We claim that \[g(n)=\lfloor\log_2(n)\rfloor+1.\] We firstly show that $g(n)\le\lfloor\log_2(n)\rfloor+1$ by induction on $\lfloor\log_2n\rfloor$. For the base case $\lfloor\log_2(n)\rfloor=0\iff n=1$, obviously $f_1(\vec a)=f_1((1))=\left\lfloor\frac11\right\rfloor=1\implies g(n)=1\le\lfloor\log_2(n)\rfloor+1$. Assume that $g(n)\le\lfloor\log_2(n)\rfloor+1=k+1$ for all $n$ such that $\lfloor\log_2(n)\rfloor=k$. Now consider those $n$ such that $\lfloor\log_2(n)\rfloor=k+1$. Indeed, we can assign \begin{align*}a_{\left\lfloor\frac n2\right\rfloor+1}&=n,\\a_{\left\lfloor\frac n2\right\rfloor+2}&=\left\lfloor\frac n2\right\rfloor+1,\\a_{\left\lfloor\frac n2\right\rfloor+3}&=\left\lfloor\frac n2\right\rfloor+2,\\&\dots,\\a_n&=n-1.\end{align*}Then \begin{align*}f_n(\vec a)&=\sum_{i=1}^{\left\lfloor\frac n2\right\rfloor}\left\lfloor\frac{a_i}i\right\rfloor+\sum_{i=\left\lfloor\frac n2\right\rfloor+1}^{n}\left\lfloor\frac{a_i}i\right\rfloor\\&=f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)+\left\lfloor\frac n{\left\lfloor\frac n2\right\rfloor+1}\right\rfloor+\sum_{i=\left\lfloor\frac n2\right\rfloor+2}^n\left\lfloor\frac{i-1}i\right\rfloor\\&=f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)+1,\end{align*}where $\vec{a'}=\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right)$ is the projection of $\vec a$, the map \[\mathbb R^n\supseteq S_n\stackrel{\phi}{\twoheadrightarrow}\left\{\vec{a'}=\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right)\right\}\subseteq\mathbb R^{\left\lfloor\frac n2\right\rfloor}\]is defined by \[\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}, a_{\left\lfloor\frac n2\right\rfloor+1}, \dots, a_n\right)\stackrel{\phi}{\twoheadrightarrow}\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right).\]Hence \begin{align*}&g(n)\\\le& f_n\left(\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}, n, \left\lfloor\frac n2\right\rfloor+1, \left\lfloor\frac n2\right\rfloor+2, \dots, n-1\right)\right)\\=&f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)+1.\end{align*}By induction hypothesis, there exists \[\vec{a'}\in \left\{\vec{a'}=\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right)\right\}\]such that \[f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)=\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor+1=k+1,\]so \[g(n)\le k+2.\] Next, we show that \[f_n(\vec a)\ge\lfloor\log_2n\rfloor+1\forall\vec a\in S_n\forall n.\] Claim 1. $f_n(\vec a)$ achieves its minimum when $\vec{a'}\in S_{\left\lfloor\frac n2\right\rfloor}$. Proof. We use the method of sharpening. Suppose that $1\le i_1, a_{i_1}\le\left\lfloor\frac n2\right\rfloor$ and $\left\lfloor\frac n2\right\rfloor+1\le i_2, a_{i_2}\le n$. Then we can compute \begin{align*}&f_n\left(\left(a_1, \dots, a_{i_1-2}, a_{i_1-1}, a_{i_2}, a_{i_1+1}, a_{i_1+2}, \dots, a_{i_2-2}, a_{i_2-1}, a_{i_1}, a_{i_2+1}, a_{i_2+2}, \dots, a_n\right)\right)-f_n\left((a_1, \dots, a_n)\right)\\=&\left(\left\lfloor\frac{a_{i_2}}{i_1}\right\rfloor+\left\lfloor\frac{a_{i_1}}{i_2}\right\rfloor\right)-\left(\left\lfloor\frac{a_{i_1}}{i_1}\right\rfloor+\left\lfloor\frac{a_{i_2}}{i_2}\right\rfloor\right)\\\ge&\left\lfloor\frac{a_{i_2}}{i_1}\right\rfloor-\left\lfloor\frac{a_{i_1}}{i_1}\right\rfloor-1\\>&\frac{a_{i_2}-a_{i_1}}{i_1}-2\\\ge&\frac11-2\\\ge&-1.\end{align*}But the value must be integral, hence \[f_n\left(\left(a_1, \dots, a_{i_1-2}, a_{i_1-1}, a_{i_2}, a_{i_1+1}, a_{i_1+2}, \dots, a_{i_2-2}, a_{i_2-1}, a_{i_1}, a_{i_2+1}, a_{i_2+2}, \dots, a_n\right)\right)-f_n\left((a_1, \dots, a_n)\right)\ge 0.\] We show the bound by induction on $\lfloor\log_2n\rfloor$ where the base case $n=1$ is vacuously true. Assume that $f_n(\vec(a))\ge\lfloor\log_2n\rfloor+1\forall\vec a\in S_n$ for those $n$ such that $\lfloor\log_2n\rfloor=k$. Then we now consider those $n$ such that $\lfloor\log_2n\rfloor=k+1$. Indeed, by Claim 1, it suffices for us to consider the cases when $\vec{a'}\in S_{\left\lfloor\frac n2\right\rfloor}$, so, we have \begin{align*}f_n(\vec a)&=f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)+\sum_{i=\left\lfloor\frac n2\right\rfloor+1}^n\left\lfloor\frac{a_i}i\right\rfloor\\&\ge k+1+\sum_{i=\left\lfloor\frac n2\right\rfloor+1}^n\left\lfloor\frac{a_i}i\right\rfloor\\&\ge k+1+\sum_{\substack{\left\lfloor\frac n2\right\rfloor+1\le i\le n\\a_i=n}}^n\left\lfloor\frac{a_i}i\right\rfloor\\&=k+1+\sum_{i=\left\lfloor\frac n2\right\rfloor+1}^n\left\lfloor\frac{a_i}i\right\rfloor\\&\ge k+1+\sum_{\substack{\left\lfloor\frac n2\right\rfloor+1\le i\le n\\a_i=n}}^n\left\lfloor\frac ni\right\rfloor\\&\ge k+1+\sum_{i=\left\lfloor\frac n2\right\rfloor+1}^n\left\lfloor\frac{a_i}i\right\rfloor\\&\ge k+1+\left\lfloor\frac nn\right\rfloor\\&=k+2\end{align*} Therefore, $g(n)=\lfloor\log_2(n)\rfloor+1$, which is what we wanted.

We claim that the smallest possible value is $\lfloor\log_2n\rfloor+1$. If $n=2^a+b$ for $b<2^a$, then let the permutation be $$1,3,2,7,4,5,6,\ldots,2^i-1.2^{i-1},2^{i-1}+1,\ldots,2^{i-1}+(2^{i-1}-1),\ldots,2^a+b,2^a,2^a+1,\ldots,2^a+(b-1).$$The only $k$ for which $a_k\geq k$ is when $k$ is a power of $2$, and $a_{2^i}=2^{i+1}-1$, so $\left\lfloor\frac{a_{2^i}}{2^i}\right\rfloor=1$. Therefore, the sum is equal to $\lfloor\log_2n\rfloor+1$ in this case. Now, we will show that $\sum_{k=1}^n\left\lfloor\frac{a_k}k\right\rfloor\geq\lfloor\log_2n\rfloor+1$ by induction on $n$. Base Case: $n=1$ The only possible value is $\left\lfloor\frac11\right\rfloor=1=\lfloor\log_21\rfloor+1$. Inductive Step: Suppose that $a_i=n=2^a+b$. Then, we have \begin{align*} \sum_{k=1}^n\left\lfloor\frac{a_k}k\right\rfloor&\geq\sum_{k=1}^{n-1}\left\lfloor\frac{a_k}k\right\rfloor\\ &=\sum_{k=1}^{k-1}\left\lfloor\frac{a_k}k\right\rfloor+\sum_{k=i+1}^{n-1}\left\lfloor\frac{a_k}k\right\rfloor+\left\lfloor\frac{a_i}i\right\rfloor\\ &\geq\sum_{k=1}^{k-1}\left\lfloor\frac{a_k}k\right\rfloor+\sum_{k=i+1}^{n-1}\left\lfloor\frac{a_k}k\right\rfloor+\left\lfloor\frac{a_n}i\right\rfloor\\ &\geq\lfloor\log_2(n-1)\rfloor+1 \end{align*}since $(a_1,a_2,\ldots,a_{i-1},a_n,a_{i+1},\ldots,a_{n-1})$ is a permutation of $(1,2,\ldots,n-1)$. Therefore, if $b\neq0$ then we have proven the inductive step. If $b=0$, then we have $$\sum_{k=1}^{2^{a-1}}\left\lfloor\frac{a_k}k\right\rfloor\geq a.$$If $i\geq2^{a-1}+1$ then $\displaystyle\left\lfloor\frac{a_i}i\right\rfloor+\sum_{k=1}^{a-1}\left\lfloor\frac{a_k}k\right\rfloor\geq a+1$, as desired. Otherwise, $$\sum_{k=1}^{2^{a-1}}\left\lfloor\frac{a_k}k\right\rfloor\geq\sum_{k=1}^{i-1}\left\lfloor\frac{a_k}k\right\rfloor+\sum_{k=i+1}^{2^{a-1}}\left\lfloor\frac{a_k}k\right\rfloor+\left\lfloor\frac{a_i-i}i\right\rfloor+1.$$Suppose that $a_{b_1}<a_{b_2}<\ldots<a_{b_{2^{a-1}-1}}$ where $b_j\neq i$ and $b_j\leq2^{a-1}$. Then, $a_{b_j}\geq j$, so this expression is at least $$\sum_{k=1}^{2^{a-1}-1}\left\lfloor\frac k{b_k}\right\rfloor+\left\lfloor\frac{2^{a-1}}i\right\rfloor+1$$since $a_i-i\geq2^{a-1}$. As $(b_1,b_2,\ldots,b_{2^{a-1}-1},i)$ is a permutation of $(1,2,\ldots,2^{a-1})$, this means that this expression is at least $a+1$, as desired. This means that the smallest possible value of $\displaystyle\sum_{k=1}^n\left\lfloor\frac{a_k}k\right\rfloor$ over all permutations of $\{1,2,\ldots,n\}$ is $\boxed{\lfloor\log_2n\rfloor+1}$.

The answer is $\boxed{\lfloor\log_2(n)\rfloor+1}.$ $\textbf{Construction: }$ We inductively construct $\{a_i\};$ the base case is easy. For the inductive step, Use the inductive hypothesis to make the first $\lfloor n/2\rfloor$ terms a permutation of $1,2,\dots,\lfloor n/2\rfloor.$ This gives a sum of $\lfloor\log_2(\lfloor n/2\rfloor)\rfloor+1=\lfloor\log_2(n)\rfloor.$ Let the $\lfloor n/2\rfloor+1$th term be $n.$ This adds $\lfloor n/(\lfloor n/2\rfloor+1)\rfloor=1.$ Let $a_k=k-1$ for all $k>\lfloor n/2\rfloor+1.$ This adds nothing to the sum. Our final sum is $\lfloor\log_2(n)+1\rfloor,$ so our induction is complete. $\textbf{Proof: }$ Induct on $n;$ the base case is clear. Let $m$ be such that $a_m=n.$ By the inductive hypothesis, \[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\ge\sum_{k=1}^{m}\left\lfloor\frac{a_k}{k}\right\rfloor\ge(\lfloor\log_2(m-1)\rfloor+1)+\lfloor n/m\rfloor=\left\lfloor\log_2\left(\frac{n}{\lfloor n/m\rfloor+1}\right)\right\rfloor+(\lfloor n/m\rfloor+1).\]If $\lfloor n/m\rfloor$ increases by $1,$ then the first term increases by at most $1$ while the second term increases by $1.$ Thus, it is always optimal for $\lfloor n/m\rfloor$ to be $1.$ This gives the desired bound of \[\lfloor\log_2(n/2)\rfloor+2=\lfloor\log_2(n)\rfloor+1.\]

Answer. $\left\lfloor \log_2 n \right\rfloor + 1$. Construction. For every integer $i\in[n]$, choose $a_i=2^{\left\lfloor\log_2 i\right\rfloor}$ whenever $i=n$ or $i+1$ is a power of $2$. Otherwise choose $a_i=i+1$. Bound. We prove the statement by strong induction on $n$. The base case $n=1$ is clear. Let $f(n)$ be the minimal value of $\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor$ over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}$. It suffices to prove that $f(n)\ge f\left(\left\lfloor\frac{n}2\right\rfloor\right) + 1$ whenever $n\ge 2$. Claim. Let $n$ be a positive integer. Let $a_1,\ldots,a_n$ be pairwise distinct positive integers. Then $\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\ge f(n)$ and if $\max(a_1,\ldots,a_n)\ge 2n$ then the inequality is strict. Proof. Pick a permutation $\sigma\in s_n$ such that $a_{\sigma(1)}<a_{\sigma(1)}<\ldots a_{\sigma(n)}$. For each $i\in[n]$ let $b_i=a_{\sigma(i)}-i$. Hence $b_i\ge 0$ and \begin{align*} \sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor &=\sum_{k=1}^{n}\left\lfloor\frac{a_{\sigma(k)}}{\sigma(k)}\right\rfloor\\ &=\sum_{k=1}^{n}\left\lfloor\frac{b_k+k}{\sigma(k)}\right\rfloor\\ &\ge\sum_{k=1}^{n}\left\lfloor\frac{k}{\sigma(k)}\right\rfloor + \sum_{k=1}^{n}\left\lfloor\frac{b_k}{\sigma(k)}\right\rfloor\\ &\ge f(n) + \left\lfloor\frac{b_n}{\sigma(n)}\right\rfloor. \end{align*}Obviously $f(n) + \left\lfloor\frac{b_n}{\sigma(n)}\right\rfloor \ge f(n)$. If $\max(a_1,\ldots,a_n)\ge 2n$ then $b_n\ge n\ge\sigma(n)$ so we obtain a strict inequality. $\square$ Now pick an integer $n\ge 2$. Pick any permutation $(a_1,\dots,a_n)$ of $\{1,\dots,n\}$. Let $m=\left\lfloor\frac{n}2\right\rfloor$. Let $t\in[n]$ be the element such that $a_t=n$. We consider two cases. Case 1. $t\ge m+1$. Then by the claim above we have \begin{align*} \sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor &=\sum_{k=1}^{m}\left\lfloor\frac{a_k}{k}\right\rfloor + \sum_{k=m+1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\\ &\ge f(m) + \left\lfloor\frac{n}{t}\right\rfloor\\ &\ge f(m) + 1. \end{align*} Case 2. $t\le m$. Then $\max(a_1,\ldots,a_m)=n\ge 2m$. Therefore, by the claim above, $$\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\ge \sum_{k=1}^{m}\left\lfloor\frac{a_k}{k}\right\rfloor \ge f(m) + 1.$$ This proves that $f(n)\ge f(m)+1$, as desired.

Here goes my solution, which seems different and is a bit sketchy, hopefully not a fakesolve. Edit: Actually, I now realize that the solution right above mine is similar and much better written.

Let the smallest possible value be $F(n)$. We show that $F(n) = 1+ \lfloor \log_2 n \rfloor$ for all naturals $n$. Note that $F(1) = 1$. It suffices to show that for all naturals $n$, we have $F(2n) = F(n) + 1$ and $F(2n+1) = F(n)+1$. We show the former. Suppose $\sigma \in \mathcal{S}_n$ achieves $\sum_{k=1}^{n}\left\lfloor\frac{\sigma(k)}{k}\right\rfloor = F(n)$. Extend $\sigma$ to $\pi \in \mathcal{S}_{2n}$ as \[\pi(k) = \begin{cases} \sigma(k) & 1 \le k \le n \\ 2n & k = n+1 \\ k-1 & n+2 \le k \le 2n \end{cases}\]Then \[\sum_{k=1}^{n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor = F(n) +\left \lfloor \frac{2n}{n+1} \right \rfloor + \sum_{k=n+2}^{2n}\left\lfloor\frac{k-1}{k}\right\rfloor = F(n)+1,\]so $F(2n) \le F(n)+1.$ Suppose $F(2n) \le F(n)$. Consider a permutation $\pi \in \mathcal{S}_{2n}$ such that $\sum_{k=1}^{2n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor = F(2n)$. Consider the first $n$ elements $\pi(1), \pi(2), \ldots, \pi(n)$. The $m$-th smallest number among these is at least $m$, for each $1 \le m \le n$. Define $\sigma \in \mathcal{S}_n$ as $\sigma(k) = m$ if $\pi(k)$ is the $m$-th smallest among $\pi(1), \pi(2), \ldots, \pi(n)$. Then, \[F(n) \ge F(2n) = \sum_{k=1}^{2n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor \ge \sum_{k=1}^{n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor \ge \sum_{k=1}^{n}\left\lfloor\frac{\sigma(k)}{k}\right\rfloor \ge F(n)\] So equality holds throughout. This means $\left\lfloor\frac{\pi(k)}{k}\right\rfloor = 0$ for $n+1 \le k \le 2n$ and $\left\lfloor\frac{\pi(k)}{k}\right\rfloor = \left\lfloor\frac{\sigma(k)}{k}\right\rfloor$ for $1 \le k \le n$. But where does the number $2n$ go? Note that $\left \lfloor\frac{2n}{k}\right\rfloor \ge 1$ for any $n+1 \le k \le 2n$, and if $\pi(k) = 2n$ for some $1 \le k \le n$, then $\left \lfloor\frac{\pi(k)}{k}\right\rfloor > \left\lfloor\frac{\sigma(k)}{k}\right\rfloor$, because the difference $\frac{\pi(k)}{k} - \frac{\sigma(k)}{k} = \frac{2n}{k} - \frac{n}{k} \ge 1$. This is a contradiction. Therefore $F(2n) = F(n) + 1$. The proof of $F(2n+1) = F(n) + 1$ is similar.

I claim that the answer is $\boxed{\lfloor \log_2n \rfloor + 1}$. Construction: We will describe a construction that yields recursively. Let $p_n$ be the $n$-tuple $p_n = (b_1, b_2, \cdots, b_n)$ that we are constructing that will give $F(b_1, b_2, \cdots, b_n) := \sum_{k=1}^{n}\left \lfloor \frac{b_k}{k}\right \rfloor = \lfloor \log_2n\rfloor + 1$. Take $p_1 = (1)$. Say $p_{n-1} = (b_1, b_2, \cdots, b_{n-1})$. Then, for $n > 1$, if $n$ is not a power of $2$, set $p_n$ to be the $n$-tuple with entries $b_i$ for $0 < i < 2^{\lfloor \log_2n\rfloor}$, entry $n$ for $i = 2^{\lfloor \log_2n\rfloor}$, entry $b_i$ for $2^{\lfloor \log_2n\rfloor} < i < n$, and entry $b_{2^{\lfloor \log_2n\rfloor}}$ for $i = n$, and if $n$ is a power of $2$, just append $n$ to the end of $p_{n-1}$, i.e. $p_n = (b_1, b_2, \cdots, b_{n-1}, n)$. To show that this works, we will use strong induction. The base case $n = 1$ is easy to see -- $1 = \left \lfloor \frac{1}{1}\right \rfloor = \lfloor \log_2n\rfloor + 1$. Now, assume $n = k$ works for some $k \geq 1$. We will show $n = k+1$ works. If $k+1$ is a power of $2$, then $$F(p_{k+1}) = F(b_1, b_2, \cdots, b_k, b_{k+1}) = \sum_{i=1}^{k}\left \lfloor \frac{b_i}{i} \right\rfloor + \left \lfloor \frac{b_{k+1}}{k+1}\right \rfloor = F(p_k) + 1 = \lfloor \log_2k\rfloor + 2 = \lfloor \log_2 k+1\rfloor + 1,$$since $k+1$ is a power of $2$ (so $\lfloor\log_2(k+1)\rfloor = 1 + \lfloor\log_2k\rfloor$). If $k+1$ is not a power of $2$, then let $p_k = (c_1, c_2, \cdots, c_k)$ and let $p_{k+1} = (b_1, b_2, \cdots, b_{k+1}) = $. Then, $$F(p_{k+1}) = F(b_1, b_2, \cdots, b_{2^{\lfloor \log_2(k+1)\rfloor}}, \cdots, b_k, b_{k+1}) = F(c_1, c_2, \cdots, c_{2^{\lfloor \log_2k\rfloor} - 1}, k+1, c_{2^{\lfloor \log_2k\rfloor} + 1}, \cdots, c_k, c_{2^{\lfloor \log_2k\rfloor}}),$$by the recursive defenition and the fact that $\lfloor \log_2(k+1)\rfloor = \lfloor \log_2k\rfloor$, as $k+1$ is not a power of $2$. This is equivalent to $$\left[\sum_{i=1}^{2^{\lfloor \log_2k\rfloor} - 1}\left \lfloor \frac{c_i}{i}\right \rfloor\right] + \left \lfloor \frac{k+1}{2^{\lfloor \log_2k\rfloor}} \right \rfloor + \left[\sum_{i=2^{\lfloor \log_2k\rfloor} + 1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor \right] + \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{k+1}\right \rfloor.$$Since $2^{\lfloor \log_2k\rfloor} \leq k < k+1 < 2^{\lfloor \log_2k\rfloor + 1}$ (since $\lfloor \log_2(k+1)\rfloor = \lfloor \log_2k\rfloor$ as $k+1$ is not a power of $2$ and $\lfloor x\rfloor \leq x < \lfloor x\rfloor + 1$), $\left \lfloor \frac{k+1}{2^{\lfloor \log_2k\rfloor}}\right \rfloor = 1$. Since $c_{2^{\lfloor \log_2k\rfloor}}$ was used in $p_k$, it is less than or equal to $k$, so it is less than $k+1$, thus $\left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{k+1}\right \rfloor = 0.$ Therefore, the expression is equivalent to $$1 + \left[\sum_{i=1}^{2^{\lfloor \log_2k\rfloor} - 1}\left \lfloor \frac{c_i}{i}\right \rfloor \right] + \left[\sum_{i=2^{\lfloor \log_2k\rfloor} + 1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor \right] = 1 - \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{2^{\lfloor \log_2k\rfloor}}\right \rfloor + \sum_{i=1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor = 1 - \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{2^{\lfloor \log_2k\rfloor}}\right \rfloor + 1 + \lfloor \log_2k\rfloor$$by the inductive hypothesis. Since $2^{\lfloor \log_2k\rfloor + 1} > k \geq c_{2^{\lfloor \log_2k\rfloor}}$, the floor is either $0$ or $1$. If $k$ is not a power of $2$, then by the recursive construction (constructing $p_k$ from $p_{k-1}$), $c_{2^{\lfloor \log_2k\rfloor}} = k$. Else, $c_{2^{\lfloor \log_2k\rfloor}} = k$ by our recursive contruction again, so $c_{2^{\lfloor \log_2k\rfloor}} = k$ either way, which is $\geq 2^{\lfloor \log_2k\rfloor}$, so the floor is at least $1$, so it must be equal to $1$. Thus, the expression is $1 + \lfloor \log_2k\rfloor = 1 + \lfloor \log_2(k+1)\rfloor$ ($k+1$ is not a power of $2$), so we have completed our inductive hypothesis and our proof of the construction is done and so the minimal value is at most $\lfloor \log_2n\rfloor + 1$. Bound: We will now show that the expression is at least $\lfloor \log_2n\rfloor + 1$, which will immediately imply the conclusion since by the construction, equality can hold. To show this, we will start with a lemma. Lemma 1: Let $M(n)$ be the minimum possible value of $F(a_1, a_2, \cdots, a_n) = \sum_{k=1}^{n}\left \lfloor \frac{a_k}{k}\right \rfloor$ over all permutations $\{a_i\}_{1\leq i\leq n}$ of $\{i\}_{1\leq i\leq n}$. Then, $M(n+1) \geq M(n)$. Proof: Let $(a_1, a_2, \cdots, a_{n+1})$ be a minimal such permutation. Then, if $a_{n+1} = n+1$, we have $$F(a_1, a_2, \cdots, a_{n+1}) = F(a_1, a_2, \cdots, a_n, n+1) = \left \lfloor \frac{n+1}{n+1}\right \rfloor + \sum_{k=1}^{n}\left \lfloor \frac{a_k}{k}\right \rfloor \geq M(n) + 1,$$by the minimality of $M(n)$. So in this case $M(n+1) \geq M(n)+1\geq M(n)$. Else, $a_{n+1} = j$ for some $j < n+1$, and $a_s = n+1$ for some $1\leq s\leq n$. Then, $\left \lfloor \frac{j}{n+1}\right \rfloor = 0$ since $j < n+1$. Letting $f = \{1, 2, \cdots, n\}\setminus \{a_1, a_2, \cdots, a_{s-1}, a_{s+1}, \cdots, a_n\}$, we have that $$F(a_1, a_2, \cdots, a_{n+1}) = \sum_{i=1}^{n+1}\left \lfloor \frac{a_i}{i}\right \rfloor = \sum_{i=1}^{n}\left \lfloor \frac{a_i}{i}\right \rfloor + \left \lfloor \frac{a_{n+1}}{n+1}\right \rfloor = \sum_{i=1}^{n}\left \lfloor \frac{a_i}{i}\right \rfloor = \left \lfloor \frac{n+1}{s}\right \rfloor + \sum_{\substack{1\leq i\leq n \\ i\neq s}}\left \lfloor \frac{a_i}{s} \right \rfloor \geq \left \lfloor \frac{f}{s}\right \rfloor + \sum_{\substack{1\leq i\leq n \\ i\neq s}}\left \lfloor \frac{a_i}{s} \right \rfloor \geq M(n),$$since $(a_1, a_2, \cdots, a_{s-1}, f, a_{s+1}, \cdots, a_n)$ is a permuatation of $(1, 2, \cdots, n)$, $n+1 > n \geq f$, and by the minimality of $M(n)$. Thus, either way, $M(n+1)\geq M(n).$ Now, from this it readily follows that $M(a) \geq M(b)$ if $a\geq b$ (since by Lemma 1, $F(a) \geq F(a-1) \geq \cdots \geq F(b+1)\geq F(b)$). Thus, in order to show $M(n) \geq \lfloor \log_2n\rfloor + 1$, it suffices to show $M(2^{\lfloor \log_2n\rfloor}) \geq \lfloor \log_2n\rfloor + 1$, i.e. it suffices to prove the statement for powers of $2$ only, so we will show $M(2^n) \geq n+1$ for all $n\geq 0$. Before we do that, we will prove another lemma which will help us in our induction. Lemma 2: Let $b_1, b_2, \cdots, b_n$ be pairwise distinct positive integers. Prove that there exists a permutation $a_1, a_2, \cdots, a_n$ of $1, 2, \cdots, n$ such that $$\sum_{i=1}^{n}\left \lfloor \frac{b_i}{i}\right \rfloor \geq \sum_{i=1}^{n}\left \lfloor \frac{a_i}{i}\right \rfloor$$and furthermore that $b_i > a_i$ for all $1\leq i\leq n$. Proof: Say the $b_i$ had an ordering $b_{i_1} < b_{i_2} < \cdots < b_{i_n}$, where $\{i_k\}_{1\leq k\leq n}$ is a permutation of $\{k\}_{1\leq k\leq n}$. Then, since the $b_i$ are positive, $b_{i_1} \geq 1$, so $b_{i_2} \geq 2$, and so on, so $b_{i_k} \geq k$ for all $1\leq k\leq n$. Thus, taking the permutation $a_1, a_2, \cdots, a_n$ such that $a_{i_k} = k$ for all $1\leq k \leq n$ gives $b_{i_n} > a_{i_n}$ and so $$\sum_{i=1}^{n}\left \lfloor \frac{b_i}{i} \right \rfloor = \sum_{i=1}^{n}\left \lfloor \frac{b_{i_n}}{i_n}\right \rfloor \geq \sum_{i=1}^{n}\left \lfloor \frac{a_{i_n}}{i_n}\right \rfloor = \sum_{i=1}^{n}\left \lfloor \frac{a_i}{i} \right \rfloor,$$as desired. Now, the induction. For $n = 0$, the only choice is $a_1 = 1$, whence $1 = \left \lfloor \frac{1}{1}\right \rfloor = 0 + 1$, so the base case is established. Now, assume the statement is true for $n = k$. We will prove that it is true for $n = k+1$. Let $(a_1, a_2, \cdots, a_{2^{k+1}})$ be a minimal $2^{k+1}$-tuple, i.e. so that $F(a_1, a_2, \cdots, a_{2^{k+1}}) = M(2^{k+1})$. Let $t$ be the unique index between $1$ and $2^{k+1}$ inclusive such that $a_t = 2^{k+1}$. If $t$ was greater than $2^k$, then $$M(2^{k+1}) = \sum_{i=1}^{2^{k+1}}\left \lfloor \frac{a_i}{i}\right \rfloor \geq \left \lfloor \frac{2^{k+1}}{t}\right \rfloor + \sum_{i=1}^{2^k}\left \lfloor \frac{a_i}{i}\right \rfloor \geq \left \lfloor \frac{2^{k+1}}{2^{k+1}}\right \rfloor + \sum_{i=1}^{2^k}\left \lfloor \frac{a_i}{i}\right \rfloor = 1 + \sum_{i=1}^{2^k}\left \lfloor \frac{a_i}{i}\right \rfloor.$$By Lemma $2$, since $a_1, a_2, \cdots, a_{2^k}$ are all pairwise distinct, there exists a permutation $c_1, c_2, \cdots, c_n$ with $$\sum_{i=1}^{2^k}\left \lfloor \frac{a_i}{i}\right \rfloor \geq \sum_{i=1}^{2^k}\left \lfloor \frac{c_i}{i}\right \rfloor \geq M(2^k),$$where the last inequality is by the minimality of $M(2^k)$. Thus, $M(2^{k+1}) \geq 1 + M(2^k)$, and since by the inductive hypothesis $M(2^k) \geq k+1$, we have $M(2^{k+1}) \geq 1 + (k+1)$, so we are done in the case that $t > 2^k$. Else, $t$ is less than or equal to $2^k$, so $$M(2^{k+1}) = \sum_{i=1}^{2^{k+1}}\left \lfloor \frac{a_i}{i}\right \rfloor \geq \sum_{i=1}^{2^k}\left \lfloor \frac{a_i}{i}\right \rfloor.$$By Lemma $2$, there exists a permutation $\{b_i\}_\{1\leq i\leq 2^k\}$ of $\{i\}_\{1\leq i\leq 2^k\}$ with $a_i \geq b_i$ for all $1\leq i\leq 2^k$. By the minimality of $M(2^k)$, $$\sum_{i=1}^{2^k}\left \lfloor \frac{b_i}{i}\right \rfloor \geq M(2^k),$$so we have $$M(2^{k+1}) - M(2^k) \geq \sum_{i=1}^{2^k}\left(\left \lfloor \frac{a_i}{i}\right \rfloor - \left \lfloor \frac{b_i}{i}\right \rfloor\right).$$Since $a_i \geq b_i$ for all $1\leq i\leq 2^k$, all of these terms are nonnegative, so this is greater than or equal to $$\left \lfloor \frac{2^{k+1}}{t} \right \rfloor - \left \lfloor \frac{b_t}{t}\right \rfloor.$$I claim that this is greater than or equal to $1$. It suffices to show that $\frac{2^{k+1}}{t} - \frac{b_t}{t}$ is $\geq 1$, since if they differ by at least $1$, they cannot reside in the same interval $[x, x+1)$ for some integer $x$, hence they have different floors (and if the difference of the floors is not greater than or equal to $1$, it must be less than $1$, but the difference is nonnegative since $2^{k+1} > b_t$, so the difference must be $0$). Indeed, $$\frac{2^{k+1} - b_t}{t} \geq \frac{2^{k+1} - 2^k}{2^k} = 1.$$Thus, $M(2^{k+1}) - M(2^k) \geq 1$. By the inductive hypothesis, $M(2^k) \geq k+1$, so it follows that $M(2^{k+1}) \geq 1 + M(2^k) \geq 1 + (k+1)$, so in both cases our inductive step is complete and so we are finally done.

My solution is almost purely combinatorial, using cycles in permutations. I think this could belong in the combo shortlist ^_^ (>_<) The answer is $f(n) = \lfloor \log_2(n) \rfloor + 1$ or given by the recurrence $f(n) = f(\lfloor n/2 \rfloor) + 1$ with $f(1) = 1.$ The construction can be exhibited recursively. For odd $n,$ we use the arrangement from $f((n-1)/2)$ for $a_1,\ldots,a_{(n-1)/2},$ then we set $a_{(n+1)/2} = n, a_{(n+1)/2+1} = \frac{n+1}{2}, a_{(n+1)/2+2} = \frac{n+1}{2} + 1,\ldots, a_n = n-1.$ Then we clearly have $f(n) = f(\lfloor n/2 \rfloor) + 1$ as the only additional contributing term is $\lfloor a_{(n+1)/2} / ((n+1)/2) \rfloor = 1.$ For even $n,$ we do something similar. We first use the arrangement from $f(n/2)$ for the first $n/2$ terms, then we set $a_{n/2 + 1} = n, a_{n/2+2} = \frac{n}{2}+1, a_{n/2+3} = \frac{n}{2}+2,\ldots, a_{n} = n-1.$ This again gives us $f(n) = f(n/2) + 1.$ Now we claim that this construction is optimal. Note that the sum $\sum_{k} \left\lfloor \frac{a_k}{k} \right\rfloor$ can be decomposed into cycles based on the permutation $(a_1,\ldots,a_n).$ Suppose $b_1 \to b_2 \to \cdots \to b_j \to b_1$ is such a cycle, contributing $\sum_{i=1}^{j} \left\lfloor \frac{b_{i}}{b_{i+1}} \right\rfloor$ to the total sum. Then I claim that in any optimal configuration, the cycle contains at most one inversion, ie. $i$ such that $b_{i} > b_{i+1}.$ To show this, suppose there were two or more inversions in the cycle. WLOG, let $b_1$ be the largest element in the cycle. Let $b_m > b_{m+1}$ be the rightmost inversion in the permutation, $m > 1.$ We will split the cycle into two cycles, removing the inversion $(b_m, b_{m+1}).$ Then we can iteratively do this to remove inversions until there is at most one remaining in each cycle. We can write the cycle in the form $$b_1 > b_2 b_3 \cdots b _{m-1} b_m > b_{m+1} < b_{m+2} < \cdots < b_j < b_1$$There are two cases. Suppose $b_m > b_j$ But then we could split the cycle into two cycles: $$b_1 > b_2 \cdots b_m < b_1 \hspace{0.5 cm} \text{ and } \hspace{0.5 cm} b_j > b_{m+1} < b_{m+2} < \cdots < b_j$$If we compare the sum of contributions from these two cycles with the sum for the original cycle, after cancelling like terms we see that the remaining terms are $\left\lfloor \frac{b_m}{b_1} \right\rfloor + \left\lfloor \frac{b_j}{b_{m+1}} \right\rfloor$ for the two cycles compared to $\left\lfloor \frac{b_m}{b_{m+1}} \right\rfloor + \left\lfloor \frac{b_j}{b_1} \right\rfloor$ for the original cycle, as these are the only terms not in common. However, $\left\lfloor \frac{b_m}{b_1} \right\rfloor = \left\lfloor \frac{b_j}{b_1} \right\rfloor = 0$ as $b_j, b_m < b_1,$ and $\left\lfloor \frac{b_j}{b_{m+1}} \right\rfloor \leq \left\lfloor \frac{b_m}{b_{m+1}} \right\rfloor$ as $b_j < b_m.$ In the special case where $b_j = b_{m+1}$ the second cycle is a degenerate fixed point $b_{m+1} \to b_{m+1}.$ Thus, the total sum does not increase after the split. Otherwise, we have $b_j > b_m,$ so $b_{m+1} < b_m < b_j.$ Then there exists $k > m$ such that $b_k > b_m$ and $b_{k-1} < b_m.$ Now we split the cycle into $$b_1 > b_2 \cdots b_{m-1} b_k < \cdots < b_j < b_1 \hspace{0.5 cm} \text{ and } \hspace{0.5 cm} b_m > b_{m+1} < \cdots < b_{k-1} < b_m$$If we compare the sum of contributions from these two cycles with sum for the original cycle, after cancelling like terms, we see that the remaining terms are $\left\lfloor \frac{b_{m-1}}{b_k} \right\rfloor + \left\lfloor \frac{b_{k-1}}{b_{m}} \right\rfloor$ for the two cycles after the split compared with $\left\lfloor \frac{b_{m-1}}{b_m} \right\rfloor + \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor$ for the original cycle. However, by assumption, $b_{k-1} < b_k$ and $b_{k-1} < b_m$ so $\left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor = \left\lfloor \frac{b_{k-1}}{b_m} \right\rfloor = 0,$ and furthermore $\left\lfloor \frac{b_{m-1}}{b_k} \right\rfloor \leq \left\lfloor \frac{b_{m-1}}{b_m} \right\rfloor$ as $b_k > b_m.$ Thus the total sum again does not increase after the split. Thus, we've shown that in some optimal permutation $(a_1,\ldots,a_k),$ each cycle $(b_k)$'s terms must be arranged in the order $b_1 > b_2 < \cdots < b_{j} < b_1,$ ie. each cycle contributes exactly one term $\left\lfloor \frac{ \max \{b_k\} }{ \min \{b_k\} } \right\rfloor$ to the total sum. Now it easily follows that optimally, each cycle must contain a set of consecutive integers, because if there were some missing number between $\min \{b_k\}$ and $\max \{b_k\}$ in some cycle, we could add that number in without affecting that contribution from that cycle, while weakly decreasing the contribution from the other cycle that we removed the number from. Then we can also show that there exists an optimal permutation where $\left\lfloor \frac{ \max \{b_k\} }{ \min \{b_k\} } \right\rfloor \leq 1$ for each cycle. Suppose some cycle contained the numbers $c,c+1,\ldots,d,$ where $d = qc + r,$ and $q \geq 2, 0 \leq r < c, $ so the contribution is $\left\lfloor \frac{d}{c} \right\rfloor = q.$ Then by splitting up into $q$ cycles of the form $(c,\ldots,2c-1), (2c,\ldots,3c-1), \ldots, (qc, \ldots, qc+r),$ we get $q$ cycles that each contribute $1,$ so the sum does not change. (We can clearly do better but this reasoning suffices.) Now by inductive hypothesis, $f(n)$ is monotonic, suppose the group containing $n$ is $k,k+1,\ldots,n$ then we know that $f(n) = \min_{\lfloor n / k \rfloor = 1} (1 + f(k-1))$ so clearly we have $k = 1+ \left\lfloor n/2 \right\rfloor,$ and we indeed have $f(n) = \lfloor \log_2(n) \rfloor + 1$ as desired. $\blacksquare$

The answer is $\lfloor \log_2{n}\rfloor + 1$. We show this in the proof. Define $f(n)$ to be the minimal value of the floor sum for a fixed $n$. There are three things to prove. $f$ is nondecreasing. $f(2^k)=k+1$. $f(2^k-1)=k$. We proceed with induction. The first condition is trivial. For the second and third conditions, we use base cases of $f(1)=1$ and $f(2)=2$ and induct. Suppose that we have $f(2^{k-1})=k$. Then to show that $f(2^k)=k+1$ we want to show that $f(2^k)=k$ is impossible. If this were true, then we would have to have $a_k<k$ for all $2^{k-1}<k\le 2^k$ which implies that $a_i=2^k$ for some $1\le i\le 2^{k-1}$. But now the floor sum of the first half of the permutation for $n=2^k$ is greater than $f(2^{k-1})=k$ which implies that $f(2^k)\ge k+1$. A construction for $k+1$ is simple: take the optimal construction for $n=2^{k-1}$ and set $a_{2^{k-1}+1}=2^k$ and $a_i=i-1$ for all $2^{k-1}+1<i\le 2^k$. Now, we want to show that $f(2^k-1)=k$. It is enough to give a construction, which is trivial: just take the optimal permutation for $n=2^{k-1}-1$ and then set $a_{2^{k-1}}=2^k-1$, and $a_i=i-1$ for all $2^{k-1}<i\le 2^k-1$. We are done. $\blacksquare$

We claim that the answer is $1+\lfloor \log_2(n)\rfloor.$ $~$ Consider the following construction: let $k=\lfloor \log_2(n)\rfloor.$ Let $a_1=1,a_2=3,a_3=2,$ and note that $2^k\le n<2^{k+1}.$ For $i\le k$ and $2^{i}< j< 2^{i+1}$ let $a_j=j-1$ and $a_{2^{i-1}}=2^i-1.$ Let $a_{2^i}=n.$ Note that $\left\lfloor\frac{a_k}{k}\right\rfloor$ is one if and only if $k$ is a power of two, and zero otherwise, so the sum is $1+\lfloor \log_2(n)\rfloor$ as desired. $~$ Now, we need to prove that this is minimal. $~$ We claim that there exists a minimum construction where $a_1=1.$ Otherwise, in a minimum construction, suppose $m$ is the value such that $a_m=1$ then \[a_1+\left\lfloor\frac{1}{m}\right\rfloor=a_1\ge 1+\left\lfloor\frac{a_1}{m}\right\rfloor\]so there is another minimum construction for which $a_1=1.$ $~$ Suppose there exists a minimum construction where $\left\lfloor\frac{a_{j-1}}{j-1}\right\rfloor\le 1$ for all $j\le i$ and suppose there is a minimum construction where $a_i\ge 2i.$ Then, let $pi\le a_i<(p+1)i.$ Now, in order to decrease the value of $\left\lfloor\frac{a_i}{i}\right\rfloor$ we find a value $q$ such that $a_q<pi$ but we also need $a_i< 2q.$ $~$ Suppose the set of $q$ such that $a_q<pi$ is disjoint from the set of $q$ such that $a_i<2q.$ There are $pi-1$ in the first set, and at least $n-\frac{(p+1)i}{2}$ in the second set. Note that summing the two with $p\ge 2$ will result in a number at least $n-1$ so that's a contradiction. Thus, there exists a described $q.$ $~$ Now, if we swap $a_i$ and $a_q$ then $\left\lfloor\frac{a_i}{i}\right\rfloor$ decreases by at least $1$ and $\left\lfloor\frac{a_q}{q}\right\rfloor$ increases by at most $1.$ Thus, we have constructed another minimal construction. Following this pattern, there exists a minimum construction where $\left\lfloor\frac{a_k}{k}\right\rfloor\le 1$ for all $k.$ $~$ It remains to find the number of values $k$ for which $a_k\ge k.$ Group the terms by $[2^k,2^{k+1}-1)$ and we are done.

Let $f(n)$ be the answer. It is clearly that $f(1)=1$. We claim that $f(n)=f\left(\left\lfloor\frac n2\right\rfloor\right)+1$. This will implay that $f(n)=\lfloor\log_2(n)\rfloor + 1$ Let $m=\left\lfloor\frac n2\right\rfloor$. Firstly, we will show that $f(n)\leq f(m)+1$. From the definition of $f$, there exists $(a_1,a_2,\hdots,a_m)$ which is a permutation of $(1,2,.\hdots,m)$ such that $\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_m}{m}\right\rfloor=f(m)$. Now, let $a_i = i-1$ for all $m+2\leq i \leq n$ and $a_{m+1}=n$. We see that $(a_1,a_2,\hdots,a_n)$ is a permutation of $(1,2,.\hdots,n)$. Hence, \begin{align*} f(n)&\leq\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_n}{n}\right\rfloor\\&=f(m)+\left\lfloor\frac{n}{m+1}\right\rfloor+\left\lfloor\frac{m+1}{m+2}\right\rfloor+\cdots+\left\lfloor\frac{n-1}{n}\right\rfloor\\ &=f(m)+1.\\ \end{align*} Now we will show that $f(n)\geq f(m)+1$; that is to show that $\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_n}{n}\right\rfloor\geq f(m)+1$ for all permutation $(a_1,a_2,\hdots,a_n)$. Note that $\left\lfloor\frac{a_i}{i}\right\rfloor\geq 0$ for all $i$. Let $1\leq k\leq n$ be an integer such that $a_k=n.$ Case 1: $k\leq m$. Let $(b_1,b_2,\cdots,b_m)$ be a permutation of $(1,2,.\hdots,m)$ such that $b_i=a_i$ if $a_i\leq m$. It is clear that this permutation exists. Thus, $a_i\geq b_i$ for all $i\leq m$ We see that $\left\lfloor\frac{a_i}{i}\right\rfloor\geq\left\lfloor\frac{b_i}{i}\right\rfloor$ for all $1\leq i\leq m$, and $\left\lfloor\frac{a_k}{k}\right\rfloor=\left\lfloor\frac{n}{k}\right\rfloor\geq\left\lfloor\frac{m}{k}\right\rfloor+\left\lfloor\frac{m}{k}\right\rfloor\geq \left\lfloor\frac{b_k}{k}\right\rfloor+1$. Therefore $\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_n}{n}\right\rfloor\geq\left\lfloor\frac{b_1}{1}\right\rfloor+\left\lfloor\frac{b_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{b_m}{m}\right\rfloor+1\geq f(m)+1$ Case 2: $k>m$. Then, $\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_n}{n}\right\rfloor\geq\left\lfloor\frac{b_1}{1}\right\rfloor+\left\lfloor\frac{b_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{b_m}{m}\right\rfloor+\left\lfloor\frac{n}{k}\right\rfloor\geq f(m)+1$ Therefore, $f(n)\geq f(m)+1$. Hence, $f(n)=f(m)+1$ as desried.

From here the smallest value can be found&proved easily by induction.

Let $f(n)$ be the smalelst possible value of our expression. We will show that $f(n) = \left\lfloor \log_2n \right\rfloor +1 $. WLOG $a_n=n-1$ otherwise swapping values doesn't change our expression. Similiarly, WLOG $a_{n-1}=n-2,a_{n-2}=n-3,...,a_{k+1}=k,a_k=n$. For some $ 2 \le k \le n$. Then we have $$f(n)= \min_{2 \le k \le n} f(k-1) + \left\lfloor \frac{n}{k} \right\rfloor \qquad (1) $$With help of $1$, calculate smaller cases of $n$. $f(1)=1,f(2)=2,f(3)=2,f(4)=3,f(5)=3,...,f(7)=3,.f(8)=4,f(9)=4,...,f(15)=4,f(16)=5...$ One may notice that reaching a power of two makes value increase by $1$, hence one may guess our answer is $$ f(n)= \left\lfloor \log_2n \right\rfloor+1 \qquad (2)$$. Which we will show by induction. The base case is indeed true. Assume it is true for all $n-1$. We will show $n$ is also true .Combining $(1),(2)$ with our induction hypothesis gives $$\min_{2 \le k \le n} \left\lfloor \log_2(k-1) \right\rfloor+ \left\lfloor \frac{n}{k} \right\rfloor \ge \left\lfloor \log_2(n)\right\rfloor \qquad (3) $$Let $n=2^x+x_1,k=2^y+y_1$ where $2^x>x_1\ge y_1$ and $ 2^y \ge y_1 \ge 1$ ( The reason $2^y \ge y_1 \ge 1$ is for avoiding to divide into cases). Rewriting $(3)$ gives $$\min \left\lfloor \log_2( 2^y+y_1-1)\right\rfloor + \left\lfloor \frac{2^x+x_1}{2^y+y_1} \right\rfloor \ge x \qquad (4)$$We can further simplify using our inequalities on our new variables. Since by floor function, we will have: $$ y+ \left\lfloor \frac{2^x+x_1}{2^y+y_1} \right\rfloor \ge x$$Which is true since $$\left\lfloor \frac{2^x+x_1}{2^y+y_1} \right\rfloor \ge \left\lfloor \frac{2^x}{2^y+2^y-1} \right\rfloor= \left\lfloor \frac{2^x}{2^{y+1}-1} \right\rfloor \ge 2^{x-(y+1)} \ge x-y$$Equality happens when $ \left\lfloor \frac{2^x+x_1}{2^y+y_1} \right\rfloor =2^{x-y-1}=x-y$ i.e when $x=y+1$ and $ y_1 = \left\lceil \frac{x_1+1}{2}\right\rceil$ since we want $y_1 > \frac{x_1}{2}$ Hence we have proven that $ f(n)= \left\lfloor \log_2n \right\rfloor+1 $ is indeed minimum value and achieveable, hence we are done.

Let $t_n$ be the minimum value of the expression; we claim that $t_n=\lfloor\log_2 n\rfloor+1$. Claim: $t_{2n}\le t_n+1$ and $t_{2n+1}\le t_n+1$. Proof. For $t_{2n}$ choose $a_i$ with $1\le i\le n$ as a permutation of $1,2,\dots n$ such that \[\sum_{i=1}^n\left\lfloor\frac{a_i}{i}\right\rfloor=t_n\]Then, let $a_{n+1}=2n$ and for $n+2\le i\le 2n$ let $a_i=i-1$. Notice our sum for $2n$ becomes $t_n+1$, so $t_{2n}\le t_n+1$. Proceed similarly for the odd case, letting $a_{n+1}=2n+1$, and we have the desired result. $\blacksquare$ Claim: $t_{2n}\neq t_n$. FTSOC, suppose not. Case 1: $a_j=2n$ with $1\le j\le n$. Notice we can find a permutation of $1,2,\dots n$ called $b_1,\dots,b_n$ such that $b_i\le a_i$ for $i\neq j$ and $b_j+n\le a_j$ since all the $a_i$ less than or equal to $n$ are distinct. Hence, \[t_n\ge \left\lfloor\frac{2n}{j}\right\rfloor+\sum_{i\neq j}\left\lfloor\frac{a_i}{i}\right\rfloor\ge 1+\left\lfloor\frac{b_j}{j}\right\rfloor+\sum_{i\neq j}\left\lfloor\frac{b_i}{i}\right\rfloor\]which contradicts the minimality of $t_n$. Case 2: $a_j=2n$ with $n+1\le j\le 2n$. Then, $\left\lfloor\frac{a_j}{j}\right\rfloor\ge 1$ and the sum of the first $n$ terms is at least $t_n$ so we have a contradiction. $\blacksquare$ Therefore, since $t_1=1$, we can prove by induction that the first term of $t$ is one, the next two terms are two, the next four terms are three, and so on, with the next $2^i$th terms being $i+1$. Thus, $t_{2^i}$ to $t_{2^{i+1}-1}$ are equal to $i+1$ so we find $t_n=\lfloor\log_2 n\rfloor+1$. $\square$

The answer is $\boxed{\lfloor\log_2n\rfloor+1}$. Strong induct on $n$; the base case is trivial. Assume the assertion holds for $1,2,\dots,n$, specifically for $\lfloor\tfrac{n+1}{2}\rfloor$ so that \[\sum_{k=1}^{\lfloor(n+1)/2\rfloor}\left\lfloor\frac{a_k}{k}\right\rfloor\le\left\lfloor\log_2\left\lfloor\frac{n+1}{2}\right\rfloor\right\rfloor+1=\lfloor\log_2(n+1)\rfloor\]where $(a_1,\dots,a_{\lfloor(n+1)/2\rfloor})$ is a permutation of $[\lfloor\tfrac{n+1}{2}\rfloor]$. It remains to show that $1$ is the minimum of the remaining \[\sum_{k=\lfloor(n+1)/2\rfloor+1}^{n+1}\left\lfloor\frac{a_k}{k}\right\rfloor.\]Indeed, said minimum is attainable at $(a_{\lfloor(n+1)/2\rfloor+1},\dots,a_{n+1})=(n+1,\lfloor\tfrac{n+1}{2}\rfloor+1,\dots,n)$, and it is optimal because clearly $a_k\ge k\iff\lfloor\tfrac{a_k}{k}\rfloor\ge1$ for some $k$. $\square$

Take a minimal sum and let $a_{f(i)} = i$. Claim: Suppose that $f(n) = t$. Then $f(k) = k + 1$ holds for $n - 1 \ge k > t$ Proof. This holds trivially if $f(n) = n$. Else, suppose that $f(n) < n$. Then, if $f(n-1) \ne n$, then by swapping $a_{f(n - 1)}$ with $a_n$ it decreases the sum as \[ \left\lfloor \frac{n-1}{f(n-1)} \right\rfloor + \left\lfloor \frac{a_n}{n} \right\rfloor > \left\lfloor \frac{a_n}{f(n-1)} \right\rfloor. \]By repeating this, we can get that $f(k) = k + 1$ for $n - 1 \ge k > f(n)$. In this case, \[ \sum_{k=1}^n \left\lfloor \frac{a_k}{k} \right\rfloor = M_{f(n)-1} + \left\lfloor \frac{n}{f(n)} \right\rfloor \]$\blacksquare$ Let the answer for a fixed $n$ be $M_n$. Claim: $M_n = \left\lfloor \log_2(n) \right\rfloor + 1$. Proof. The base case of $M_1 = 1$ holds. Suppose this holds for $1, 2, \dots n$. Then $M_{n+1}$ is the minimal possible value of $\left\lfloor \log_2(k-1) \right\rfloor + \left\lfloor \frac{n+1}{k} \right\rfloor + 1$ as $k$ ranges from $1$ to $n$ inclusive. Note that this can only attain a minimum when $t$ is one more than a power of $2$, so let $k = 2^b$. The expression is then \[ b + \left\lfloor \frac{n+1}{2^b} \right\rfloor \]Since $n + 1 \ge 2^b$ it follows that this occurs when $b$ is maximized at $\left\lfloor \log_2(n+1) \right\rfloor$, at which point $\left\lfloor \frac{n+1}{2^b} \right\rfloor = 1$ so the expression is simply the desired $\left\lfloor \log_2(n+1) \right\rfloor + 1$. $\blacksquare$

"Everything is Combo" - Black Teaches Red 2023. The smallest possible value is $f(n) = \left\lfloor \log_2 n \right\rfloor + 1$. Claim: For all $n \ge 1$, we have $f(2n+1) = f(2n) = f(n) + 1$. Proof. Consider an arbitrary permutation $(b_1, b_2, \ldots, b_{2n})$ of $\{1, \ldots, 2n\}$. Let $S = \{b_k > n \mid 1 \le k \le n\}$ and $T = \{b_k \le n \mid n < k \le 2n \}$. It's easy to see $|S| = |T|,$ so there exists a bijection that swaps each element in $S$ with an element from $T$ within the permutation, forming a new permutation $(c_1, c_2, \ldots, c_{2n})$ where the first $n$ terms are a permutation of $\{1, \ldots, n\}$ and the last $n$ terms are a permutation of $\{n+1, n+2, \ldots, 2n\}$. Now, suppose $b_i = 2n$. If $1 \le i \le n$, then assume $b_i$ and $b_j$ swap via the bijection. Because $b_j \le n$, $$\sum_{k = 1}^{2n} \left\lfloor \frac{b_k}{k} \right\rfloor \ge \sum_{k = 1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor = \sum_{k = 1}^{i-1} \left\lfloor \frac{b_k}{k} \right\rfloor + \sum_{k = i+1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor + \left\lfloor \frac{2n}{i} \right\rfloor$$$$\ge \sum_{k = 1}^{i-1} \left\lfloor \frac{b_k}{k} \right\rfloor + \sum_{k = i+1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor + \left\lfloor \frac{n + b_j}{i} \right\rfloor$$$$\ge \sum_{k = 1}^{i-1} \left\lfloor \frac{b_k}{k} \right\rfloor + \sum_{k = i+1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor + \left\lfloor \frac{b_j}{i} \right\rfloor + 1 \ge \sum_{k = 1}^{n} \left\lfloor \frac{c_k}{k} \right\rfloor + 1 \ge f(n) + 1$$where the penultimate inequality is true because the bijection always swaps in smaller values for the first $n$ terms. If $n < i \le 2n$, then $$\sum_{k = 1}^{2n} \left\lfloor \frac{b_k}{k} \right\rfloor \ge \sum_{k = 1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor + \left\lfloor \frac{2n}{i} \right\rfloor \ge \sum_{k = 1}^{n} \left\lfloor \frac{c_k}{k} \right\rfloor + 1 \ge f(n) + 1$$using similar reasoning from the previous case. Thus, $f(2n) \ge f(n) + 1$. An analogous process shows the same bound for $f(2n+1)$, as we can just replace $2n$ with $2n+1$. Now, we provide a construction for equality. Let $(b_1, b_2, \ldots, b_n)$ be a permutation of $\{1, \ldots, n\}$ that achieves $\sum_{k = 1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor = f(n)$. Then, setting $(b_{n+1}, b_{n+2}, b_{n+3}, \ldots, b_{2n}) = (2n, n+1, n+2, \ldots, 2n-1)$ yields $$\sum_{k = 1}^{2n} \left\lfloor \frac{b_k}{k} \right\rfloor = \sum_{k = 1}^{n} \left\lfloor \frac{b_k}{k} \right\rfloor + \left\lfloor \frac{2n}{n+1} \right\rfloor = f(n) + 1.$$An analogous construction can be used for $2n+1$ to achieve $f(2n+1) = f(n) + 1$. $\square$ To finish, we prove the explicit formula inductively, noting the base case $f(1) = 1$ is trivial. Suppose the hypothesis is true for all $n$ such that $2^{m-1} \le n \le 2^m - 1$. Observe that $2^m \le \{2r, 2r+1\} \le 2^{m+1} - 1$ implies $2^{m-1} \le r \le 2^m - 1$ for integer $r$, so $$f(2r + 1) = f(2r) = f(r) + 1 = \left( \left\lfloor \log_2 r \right\rfloor + 1 \right) + 1 = m + 1$$$$= \left\{ \left\lfloor \log_2 (2r) \right\rfloor + 1, \left\lfloor \log_2 (2r+1) \right\rfloor + 1 \right\}$$which completes the induction step. $\blacksquare$ Remark: I should've said $2^m \le r \le 2^{m+1} - 1$ implies $2^{m-1} \le \left\lfloor \frac{r}{2} \right\rfloor \le 2^{m} - 1$ during my induction step, as the main claim is equivalent to $f(r) = f\left(\left\lfloor \frac{r}{2} \right\rfloor\right) + 1$.

We claim the answer $\left\lfloor \log_2 n\right\rfloor +1.$ Bound. From inequality $2^t\geq t+1$ we trivially conclude $\left\lfloor \frac ab\right\rfloor \geq \log_2 \frac{a+1}{b}$ for arbitrary $a,b\in \mathbb Z ^+.$ Hence $$\sum_{k=1}^{n}\left\lfloor \frac{a_k}{k}\right\rfloor \geq \sum_{k=1}^{n} \left( \log_2 \frac{a_k+1}{k} \right) =\log_2 \frac{(n+1)!}{n!}=\log_2 (n+1) >\left\lfloor \log_2 n\right\rfloor \implies \sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor \geq \left\lfloor \log_2 n\right\rfloor +1 \quad \Box$$ Construction. Split all numbers onto tuples of type $(2^i,2^i+1,\ldots ,2^{i+1}-1)$ for $i=0,1,\ldots ,\left\lfloor \log_2 n\right\rfloor$ (the last tuple may be incomplete); in each tuple consider permutation $(b_1,b_2, \ldots ,b_k)\to (b_k,b_1, \ldots ,b_{k-1}).$ Then the sum of floors in each tuple equals to $1,$ giving the exact desired total sum.

Incredibly boring problem. Smoothing basically trivializes, but the finish is actually quite tricky. The answer is $\lfloor \log_2 n \rfloor + 1$. We prove this by strong induction on $n$. Denote by $f(\sigma)$ the value of the given function, and $f(n)$ to be the minimum value for $n$ variables. Suppose that $a_k = n$. By swapping $n-1$ to $a_n$ and so on until we can no longer do so, we have $$f(\sigma) \geq f(k-1) + \left \lfloor \frac nk \right \rfloor.$$The rest is just a very long calculation: it suffices to show that $$\lfloor \log_2(k-1)\rfloor + \left \lfloor \frac nk \right \rfloor \geq \lfloor \log_2 n \rfloor.$$Unless $k$ is a power of $2$, the result follows by the identity $2^x \geq 2x$. If $k$ is a power of $2$, then we can set $k = 2^r$ and $n = 2^r q + c$, and the result follows again by a direct calculation.

// I spent like 15-20 min to bash out what the answer should be and next 10 min to find how to achieve $\left\lfloor \log_2 n\right\rfloor +1.$ and finish the problem the idea is prove using induction for $n=2^k$ , and the result for every $n$ follows easily. the constructiom is also quite easy with all the numbers between $2^k$ and $2^{k+1}$ all of the form $\frac{n-1}{n} .. \frac{n}{n+1}...$ and the last fraction gives the only $1$ to a sum

We claim that the minimum value is $1+\lfloor\log_2(n)\rfloor$. Construction: Let $k=\lfloor\log_2(n)\rfloor$. Then, $2^k\leq n\leq 2^{k+1}$. Partition the set $\{1,2,\ldots,n\}$ into sets $\{1\}, \{2,3\}, \ldots,\left\{2^k,\ldots,n\right\}$. There are exactly $k+1$ parts. Label the sets $S_0,S_1,\ldots, S_k$ such that $S_i=\{x\leq n, 2^i\leq x<2^{i+1}\}$. Then, for any $1\leq j\leq n$, if $j\in S_i$ and $j>2^i$ then $a_j=j-1$, while if $j=2^i$ then $a_j=\max(S_i)$. Using this construction, we see that if $j$ is not a power of two then $\left\lfloor\frac{a_j}{j}\right\rfloor=0$. So, the sum is just \[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor=\sum_{i=0}^{k}\left\lfloor\frac{\max(S_i)}{2^i}\right\rfloor=\sum_{i=0}^{k}1=k+1\]Note that this is because $\max(S_i)\leq2^{i+1}-1\Longrightarrow1<\frac{\max(S_i)}{2^i}<2$. So, the construction is complete. $\blacksquare$ Proof of Bound: We use induction. Base case $n=1, n=2$ are trivial. Let $m=\left\lfloor\frac n2\right\rfloor$. If $a_t=n$ for some $t>m$, then we are done because $\frac {a_t}t$ contributes at least 1, and we get the rest from $a_1, a_2, \ldots, a_m$. Now suppose that $a_t=n$ for some $t\leq m$. Let $u$ be the smallest number not in $a_1,a_2,\ldots, a_m$. If we replace $a_t$ with $u$, the answer for first $m$ terms' sum will be at least $k$. Changing back to $n$, we see that $\frac{n}{t}\geq\frac{2m}{t}\geq\frac{m+u}{t}\geq1$, and hence the answer increases by 1, which gives $k+1$. $\blacksquare$

The answer is $\lfloor \log_2 (n) \rfloor + 1$. The construction is similar to above posts. For convenience, define $f(x)$ so that $f(a_i)=i$. Say that $t \in \{ 1, 2, \dots, n \}$ is bad if $\left\lfloor \frac t{f(t)} \right\rfloor$ is positive (i.e. $t \geq f(t)$), and good otherwise. Label all the bad integers $b_1 < b_2 < \dots < b_k = n$. Then order all the $f(b_i)$ as $d_1 < d_2 < \dots < d_k$. Claim. We have $d_1 = 1$ and $d_i \leq b_{i-1} + 1$ for $i = 2, 3, \dots, k$. Proof. The first part is trivial; for second part, suppose $d_i > b_{i-1} + 1$, then at most $i-1$ elements in $\{ 1, 2, \dots, b_{i-1} + 1 \}$ are of the form $f(b)$ for $b$ bad, and so there remains at least $b_{i-1} - i + 2$ elements that are of the form $f(a)$ for $a$ good. But since here $f(a) > a$ we must have $a \in \{ 1, 2, \dots, b_{i-1} \} \setminus \{b_1, b_2, \dots, b_{i-1}\}$, so there are at most $b_{i-1} - i + 1$ possible values of $a$, contradiction. $\square$ Combining this claim with the fact that $f(b_i) \leq b_i$, one sees that we must have $d_i = f(b_i)$ for $i = 1, 2, \dots, k$. Hence it suffices to minimize \[ S = \left\lfloor \frac{b_1}{b_0+1} \right\rfloor + \left\lfloor \frac{b_2}{b_1+1} \right\rfloor + \left\lfloor \frac{b_3}{b_2+1} \right\rfloor + \dots + \left\lfloor \frac{b_k}{b_{k-1}+1} \right\rfloor \]for a sequence $0 = b_0 < b_1 < b_2 < \dots < b_k = n$. By telescoping the inequality \[ \frac{b_{i} + 1}{b_{i-1} + 1} \leq \left\lfloor \frac{b_i}{b_{i-1}+1} \right\rfloor + 1 \]we obtain \[ n + 1 \leq (s_1 + 1)(s_2 + 1) \dots (s_k + 1) \]where $s_i = \left\lfloor \frac{b_i}{b_{i-1}+1} \right\rfloor$, and we want to minimize $S = s_1 + s_2 + \dots + s_k$. Noting that if $s_i \geq 2$ then replacing it into two smaller numbers summing to $s_i$ (and correspondingly increase $k$ by $1$) must increase the RHS, so we may assume all $s_i = 1$. this produces $n + 1 \leq 2^k$ and so $S = k \geq \lfloor \log_2 (n) \rfloor + 1$, as desired.

I will propose a recursive proof to this problem. The construction will be omitted. Let $f(n)$ denote the smallest possible value over all permutations of $\{1,2,...,n\}$. Claim: $f(n)=f(i-1)+\lfloor \frac{n}{i} \rfloor$ for some natural number $i\leq n$, such that $f(n)$ is minimized, where $n$ is a natural number. We will also assume $f(0)=0$ for convenience. Moreover, I just realized that this claim was used in Evan's solution, just that I express it in a more convoluted way. Proof: Suppose $a_i=n$, then we will show that the permutation with the smallest value is indeed in the form $\{a_1,a_2,...,a_{i-1},n,i,i+1,...,n-1\}$. Let the smallest value among all the sequences with $a_i=n$ be $\{b_1,b_2,...,b_n\}$ with $b_i=n$. Then suppose $b_j$ is the largest index $j$ that doesn't satisfy this. Note that for indices $k$ larger than $j$, $b_k=k-1$. Consider swapping $b_j$ and $b_m$, where $b_m=j-1$. Note again that $j>m$ and $m\neq i$. Then the relevant fractions become: $\lfloor \frac{b_j}{m}\rfloor +\lfloor\frac{b_m}{j}\rfloor$=$\lfloor \frac{b_j}{m}\rfloor +\lfloor\frac{j-1}{j}\rfloor \leq \lfloor \frac{b_m}{m}\rfloor\leq \lfloor \frac{b_m}{m}\rfloor+\lfloor \frac{b_j}{j}\rfloor$ which is our original two fractions, implying the existence of a permutation resulting in a smaller value, contradiction. Hence, we have shown that the permutation with the smallest value is indeed in the form $\{a_1,a_2,...,a_{i-1},n,i,i+1,...,n-1\}$. Now it suffices to consider permutations of such form. Note that $\{a_1,a_2,...,a_{i-1}\}$ is actually a permutation of the first $i-1$ natural numbers. Thus for each $i$, the permutation yielding the smallest value is $\{c_1,c_2,...,c_{i-1},n,i,i+1,...,n-1\}$, where $\{c_1, c_2,...,c_{i-1}\}$ yields $f(i-1)$. Thus the permutation yielding $f(n)$ must be in that form, and $f(n)=f(i-1)+\lfloor \frac{n}{i} \rfloor$, since all the fractions before $a_i$ yield the value $f(i-1)$, while the fractions after have numerator one less than the denominator, so all the terms yield $0$. It is then clear that we choose the $i$ that yields the smallest value. We then claim that the answer is $\lfloor log_2 (n)\rfloor+1$, and will prove by induction. We will use without proof that $2^s\geq s+1$ for nonnegative integers $s$. Suppose $2^k\leq n<2^{k+1}$, and $2^m\leq i-1<2^{m+1}$ with $k<m$ and $m$ being nonnegative (i.e. i\geq 2), then $f(n)=f(i-1)+\lfloor \frac{n}{i} \rfloor\geq f(2^{m+1}-1)+\lfloor \frac{2^k}{2^{m+1}}\rfloor\geq (m+1)+2^{k-m-1}\geq m+1+(k-m-1)+1=k+1$. Then if $i=1$, it is clear that the resulting sum will be $n$. Else, $k=m$, which yields $f(n)=f(i-1)+\lfloor \frac{n}{i} \rfloor\geq k+1+\lfloor \frac{n}{n}\rfloor>k+1$. Thus, we are finished with the proof.

We go by induction base case of $n=1$ is trivial. Now assume that the claim holds for all $t\leq n$. then observe that if we let $a_i = n$ then we can put $a_t = t+1$ for all $i+1 \leq t \leq n$. then the later brackets go to zero and we are left with \begin{center} $f(n) = f(t-1) + \lfloor \frac{n}{t} \rfloor$ $\Longleftrightarrow f(n) = \lfloor log_{2} (t-1)\rfloor +1+ \lfloor \frac{n}{t} \rfloor$ \end{center} Now we make cases $\textbf{Case 1:} \frac{n}{2} \leq t \leq n$. then we have \begin{center} $f(n) \geq \lfloor log_{2} (\lceil \frac{n+1}{2}\rceil -1)\rfloor +1+ \lfloor \frac{n}{\lceil \frac{n+1}{2}\rceil} \rfloor \geq \lfloor log_{2}n\rfloor +1 $ \end{center} $\textbf{Case 2:}$ $ 1 \leq t < \frac{n}{2}$. Here we have \begin{align} \lfloor log_{2} (t-1)\rfloor +1+ \lfloor \frac{n}{t} \rfloor \geq \lfloor log_{2}n\rfloor + 1 \Longleftrightarrow \lfloor \frac{n}{t} \rfloor \geq \lfloor log_{2}n\rfloor - \lfloor log_{2} (t-1)\rfloor \Longleftrightarrow \lfloor \frac{n}{t} \rfloor \geq \lfloor log_{2}(\frac{n}{t-1} \rfloor) +1 \end{align}and this follows due to case two. We are done.

Suppose we have $a_k = n$, the maximum value. Then if $a_m = n-1$, since \[\left\lfloor\frac{n-1}{m}\right\rfloor + \left\lfloor\frac{a_n}{n}\right\rfloor \ge \left\lfloor\frac{a_n}{m}\right\rfloor + \left\lfloor\frac{n-1}{n}\right\rfloor \impliedby n-1 \ge a_n\] is true, we can optimize by swapping indices $m$ and $n-1$ to make $a_n = n-1$. Similarily, we continue this process to make \[a_{n-1} = n-2, \ldots, a_{k+1} = k.\] Define $f(n)$ as the least possible value of the desired. Then \[f(n) = \min_{1 \leq k \leq n} \left(f(k-1) + \left\lfloor\frac nk\right\rfloor\right).\] We claim our answer is $\boxed{\lfloor\log_2n\rfloor+1}$, which we can prove through induction. Suppose $a \leq n$ such that \[\left\lfloor\frac{n}{a+1}\right\rfloor+1 \leq k \leq \left\lfloor\frac{n}{a}\right\rfloor\]\[\implies f(n) = \min_{1 \leq a \leq n} \left(\left\lfloor\log_2 \left\lfloor\frac{n}{a+1}\right\rfloor\right\rfloor+a+1\right).\] We claim this is a decreasing function in $a$, and thus the maximum occurs at $a=1$. Comparing $a=x$ and $a=x+1$, it suffices to have \[\left\lfloor\frac{n}{x+1}\right\rfloor \leq 2 \left\lfloor\frac{n}{x+2}\right\rfloor,\] which indeed holds for $n > x+1$. Hence \[f(n) = \left\lfloor \log_2 \left\lfloor\frac{n}{2}\right\rfloor\right\rfloor + 2 = \left\lfloor\log_2 n\right\rfloor+1\] from casework on the parity of $n$, completing our induction. $\blacksquare$