Taiwan IMO Selection Camp, 2022

Suppose that $2^k \le n < 2^{k+1}$ with some non-negative integer $k$. First we show a permutation $(a_1, a_2, \dots, a_n)$ such that $\sum_{i=1}^n \lfloor \frac{a_i}{i} \rfloor = k+1$; then we will prove that $\sum_{i=1}^n \lfloor \frac{a_i}{i} \rfloor \ge k+1$ for every permutation. Hence, the minimal possible value will be $k+1$.

I.
Consider the permutation
$$(a_1) = (1), \quad (a_2, a_3) = (3, 2), \quad (a_4, a_5, a_6, a_7) = (7, 4, 5, 6), \quad \dots \\ (a_{2^{k+1}}, \dots, a_{2^k-1}) = (2^k - 1, 2^{k-1}, 2^{k-1} + 1, \dots, 2^k - 2), \\ (a_{2^k}, \dots, a_n) = (n, 2^k, 2^k + 1, \dots, n-1).$$
This permutation consists of $k+1$ cycles. In every cycle $(a_p, \dots, a_q) = (q, p, p+1, \dots, q-1)$ we have $q < 2p$, so
$$\sum_{i=p}^{q} \lfloor \frac{a_i}{i} \rfloor = \lfloor \frac{q}{p} \rfloor + \sum_{i=p+1}^{q} \lfloor \frac{i-1}{i} \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 1. If $b_1, \dots, b_{2^k}$ are distinct positive integers then
$$\sum_{i=1}^{2^k} \lfloor \frac{b_i}{i} \rfloor \ge k + 1.$$
From the Claim it follows immediately that $\sum_{i=1}^{n} \lfloor \frac{a_i}{i} \rfloor \ge \sum_{i=1}^{2^k} \lfloor \frac{a_i}{i} \rfloor \ge k + 1$.

Proof of Claim 1. Apply induction on $k$. For $k=1$ the claim is trivial, $\lfloor \frac{b_1}{1} \rfloor \ge 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 \le 2^{k+1}$ and $b_j \ge j$, then
$$\sum_{i=1}^{2^{k+1}} \lfloor \frac{b_i}{i} \rfloor \ge \sum_{i=1}^{2^k} \lfloor \frac{b_i}{i} \rfloor + \lfloor \frac{b_j}{j} \rfloor \ge (k+1) + 1$$
by the induction hypothesis, so the Claim is satisfied.

Otherwise we have $b_j < j \le 2^{k+1}$ for every $2^k < j \le 2^{k+1}$. Among the $2^{k+1}$ distinct numbers $b_1, \dots, b_{2^{k+1}}$ there is some $b_m$ which is at least $2^{k+1}$; that number must be among $b_1, \dots, b_{2^k}$. Hence, $1 \le m \le 2^k$ and $b_m \ge 2^{k+1}$.

We will apply the induction hypothesis to the numbers
$$c_1 = b_1, \dots, c_{m-1} = b_{m-1}, \quad c_m = b_{2^k+1}, \quad c_{m+1} = b_{m+1}, \dots, c_{2^k} = b_{2^k},$$
so take the first $2^k$ numbers but replace $b_m$ with $b_{2^k+1}$. Notice that
$$\lfloor \frac{b_m}{m} \rfloor \ge \lfloor \frac{2^{k+1}}{m} \rfloor = \lfloor \frac{2^k + 2^k}{m} \rfloor \ge \lfloor \frac{b_{2^k+1} + m}{m} \rfloor = \lfloor \frac{c_m}{m} \rfloor + 1.$$
For the other indices $i$ with $1 \le i \le 2^k$, $i \ne m$ we have $\lfloor \frac{b_i}{i} \rfloor = \lfloor \frac{c_i}{i} \rfloor$, so
$$\sum_{i=1}^{2^k+1} \lfloor \frac{b_i}{i} \rfloor = \sum_{i=1}^{2^k} \lfloor \frac{b_i}{i} \rfloor \ge \sum_{i=1}^{2^k} \lfloor \frac{c_i}{i} \rfloor + 1 \ge (k+1) + 1.$$
That proves Claim 1.

By I and II, we complete the solution.

We present a different proof for the lower bound.

Assume again $2^k \le n < 2^{k+1}$, and let $P = \{2^0, 2^1, \dots, 2^k\}$ be the set of powers of 2 among $1, 2, \dots, n$. Call an integer $i \in \{1, 2, \dots, n\}$ and the interval $[i, a_i]$ good if $a_i \ge i$.

Lemma 1. The good intervals cover the integers $1, 2, \dots, n$.

Proof. Consider an arbitrary $x \in \{1, 2, \dots, n\}$; we want to find a good interval $[i, a_i]$ that covers $x$; i.e., $i \le x \le a_i$. Take the cycle of the permutation that contains $x$, that is $(x, a_x, a_{a_x}, \dots)$. In this cycle, let $i$ be the first element with $a_i \ge x$; then $i \le x \le a_i$. $\square$

Lemma 2. If a good interval $[i, a_i]$ covers $p$ distinct powers of 2 then $\lfloor \frac{a_i}{i} \rfloor \ge p$; more formally, $\lfloor \frac{a_i}{i} \rfloor \ge |[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} \ge 2^{p-1} \ge P$; that proves the lemma. $\square$

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

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

Lemma 3.
$$\lfloor \frac{a}{b} \rfloor \ge \log_2 \frac{a+1}{b}$$
for every pair $a, b$ of positive integers.

Proof. Let $t = \lfloor \frac{a}{b} \rfloor$, so $t \le \frac{a}{b}$ and $\frac{a+1}{b} \le t + 1$. By applying the inequality $2^t \ge t + 1$, we obtain $\lfloor \frac{a}{b} \rfloor = t \ge \log_2(t+1) \ge \log_2 \frac{a+1}{b}$. $\Box$

By applying the lemma to each term, we get
$$\sum_{i=1}^{n} \lfloor \frac{a_i}{i} \rfloor \ge \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, \dots, a_n + 1$ form a permutation of $2, 3, \dots, 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} \lfloor \frac{a_i}{i} \rfloor \ge \log_2(n+1) > k.$$
As the left-hand side is an integer, it must be at least $k + 1$. $\Box$