, 2021

Answer: The minimum of such sums is $\left\lfloor\log _{2} n\right\rfloor+1$; so if $2^{k} \leqslant n<2^{k+1}$, the minimum is $k+1$.

Solution 1. Suppose that $2^{k} \leqslant n<2^{k+1}$ with some nonnegative integer $k$. First we show a permutation $(a_{1}, a_{2}, \ldots, a_{n})$ such 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=k+1$$
then we will prove 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 \geqslant k+1$$
for every permutation. Hence, the minimal possible value will be $k+1$.

I. Consider the permutation
$$\begin{gathered} (a_{1})=(1), \quad(a_{2}, a_{3})=(3,2), \quad(a_{4}, a_{5}, a_{6}, a_{7})=(7,4,5,6), \quad \ldots \\ (a_{2^{k-1}}, \ldots, a_{2^{k}-1})=(2^{k}-1,2^{k-1}, 2^{k-1}+1, \ldots, 2^{k}-2), \\ (a_{2^{k}}, \ldots, a_{n})=(n, 2^{k}, 2^{k}+1, \ldots, n-1), \end{gathered}$$
This permutation consists of $k+1$ cycles. In every cycle $(a_{p}, \ldots, a_{q})=(q, p, p+1, \ldots, q-1)$ we have $q<2p$, so
$$\sum_{i=p}^{q}\left\lfloor\frac{a_{i}}{i}\right\rfloor=\left\lfloor\frac{q}{p}\right\rfloor+\sum_{i=p+1}^{q}\left\lfloor\frac{i-1}{i}\right\rfloor=1$$
The total sum over all cycles is precisely $k+1$.

II. In order to establish the lower bound, we prove a more general statement.

Claim. If $b_{1}, \ldots, b_{2^{k}}$ are distinct positive integers then
$$\sum_{i=1}^{2^{k}}\left\lfloor\frac{b_{i}}{i}\right\rfloor \geqslant k+1$$
From the Claim it follows immediately that $\sum_{i=1}^{n}\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant \sum_{i=1}^{2^{k}}\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant k+1$.

Proof of the Claim. Apply induction on $k$. For $k=1$ the claim is trivial, $\left\lfloor\frac{b_{1}}{1}\right\rfloor \geqslant 1$. Suppose the Claim holds true for some positive integer $k$, and consider $k+1$.
If there exists an index $j$ such that $2^{k}<j \leqslant 2^{k+1}$ and $b_{j} \geqslant j$ then
$$\sum_{i=1}^{2^{k+1}}\left\lfloor\frac{b_{i}}{i}\right\rfloor \geqslant \sum_{i=1}^{2^{k}}\left\lfloor\frac{b_{i}}{i}\right\rfloor+\left\lfloor\frac{b_{j}}{j}\right\rfloor \geqslant(k+1)+1$$
by the induction hypothesis, so the Claim is satisfied.
Otherwise we have $b_{j}<j \leqslant 2^{k+1}$ for every $2^{k}<j \leqslant 2^{k+1}$. Among the $2^{k+1}$ distinct numbers $b_{1}, \ldots, b_{2^{k+1}}$ there is some $b_{m}$ which is at least $2^{k+1}$; that number must be among $b_{1} \ldots, b_{2^{k}}$. Hence, $1 \leqslant m \leqslant 2^{k}$ and $b_{m} \geqslant 2^{k+1}$.
We will apply the induction hypothesis to the numbers
$$c_{1}=b_{1}, \ldots, c_{m-1}=b_{m-1}, \quad c_{m}=b_{2^{k}+1}, \quad c_{m+1}=b_{m+1}, \ldots, c_{2^{k}}=b_{2^{k}}$$
so take the first $2^{k}$ numbers but replace $b_{m}$ with $b_{2^{k}+1}$. Notice that
$$\left\lfloor\frac{b_{m}}{m}\right\rfloor \geqslant\left\lfloor\frac{2^{k+1}}{m}\right\rfloor=\left\lfloor\frac{2^{k}+2^{k}}{m}\right\rfloor \geqslant\left\lfloor\frac{b_{2^{k}+1}+m}{m}\right\rfloor=\left\lfloor\frac{c_{m}}{m}\right\rfloor+1$$
For the other indices $i$ with $1 \leqslant i \leqslant 2^{k}, i \neq m$ we have $\left\lfloor\frac{b_{i}}{i}\right\rfloor=\left\lfloor\frac{c_{i}}{i}\right\rfloor$, so
$$\sum_{i=1}^{2^{k+1}}\left\lfloor\frac{b_{i}}{i}\right\rfloor=\sum_{i=1}^{2^{k}}\left\lfloor\frac{b_{i}}{i}\right\rfloor \geqslant \sum_{i=1}^{2^{k}}\left\lfloor\frac{c_{i}}{i}\right\rfloor+1 \geqslant(k+1)+1$$
That proves the Claim and hence completes the solution.

Solution 2. We present a different proof for the lower bound.
Assume again $2^{k} \leqslant n<2^{k+1}$, and let $P=\{2^{0}, 2^{1}, \ldots, 2^{k}\}$ be the set of powers of 2 among $1,2, \ldots, n$. Call an integer $i \in\{1,2, \ldots, n\}$ and the interval $[i, a_{i}]$ good if $a_{i} \geqslant i$.

Lemma 1. The good intervals cover the integers $1,2, \ldots, n$.
Proof. Consider an arbitrary $x \in\{1,2 \ldots, n\}$; we want to find a good interval $[i, a_{i}]$ that covers $x$; i.e., $i \leqslant x \leqslant a_{i}$. Take the cycle of the permutation that contains $x$, that is $(x, a_{x}, a_{a_{x}}, \ldots)$. In this cycle, let $i$ be the first element with $a_{i} \geqslant x$; then $i \leqslant x \leqslant a_{i}$.

Lemma 2. If a good interval $[i, a_{i}]$ covers $p$ distinct powers of 2 then $\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant p$; more formally, $\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant |[i, a_{i}] \cap P|$.
Proof. The ratio of the smallest and largest powers of 2 in the interval is at least $2^{p-1}$. By Bernoulli's inequality, $\frac{a_{i}}{i} \geqslant 2^{p-1} \geqslant p$; that proves the lemma.

Now, by Lemma 1, the good intervals cover $P$. By applying Lemma 2 as well, we obtain that
$$\sum_{i=1}^{n}\left\lfloor\frac{a_{i}}{i}\right\rfloor=\sum_{i \text{ is good }}^{n}\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant \sum_{i \text{ is good }}^{n}|[i, a_{i}] \cap P| \geqslant |P|=k+1.$$

Solution 3. We show yet another proof for the lower bound, based on the following inequality.

Lemma 3.
$$\left\lfloor\frac{a}{b}\right\rfloor \geqslant \log _{2} \frac{a+1}{b}$$
for every pair $a, b$ of positive integers.

Proof. Let $t=\left\lfloor\frac{a}{b}\right\rfloor$, so $t \leqslant \frac{a}{b}$ and $\frac{a+1}{b} \leqslant t+1$. By applying the inequality $2^{t} \geqslant t+1$, we obtain
$$\left\lfloor\frac{a}{b}\right\rfloor=t \geqslant \log _{2}(t+1) \geqslant \log _{2} \frac{a+1}{b}$$
By applying the lemma to each term, we get
$$\sum_{i=1}^{n}\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant \sum_{i=1}^{n} \log _{2} \frac{a_{i}+1}{i}=\sum_{i=1}^{n} \log _{2}(a_{i}+1)-\sum_{i=1}^{n} \log _{2} i$$
Notice that the numbers $a_{1}+1, a_{2}+1, \ldots, a_{n}+1$ form a permutation of $2,3, \ldots, n+1$. Hence, in the last two sums all terms cancel out, except for $\log _{2}(n+1)$ in the first sum and $\log _{2} 1=0$ in the second sum. Therefore,
$$\sum_{i=1}^{n}\left\lfloor\frac{a_{i}}{i}\right\rfloor \geqslant \log _{2}(n+1)>k$$
As the left-hand side is an integer, it must be at least $k+1$.