IMO 1978 Problem 5
The expression involves a weighted sum of distinct positive integers $f(1),\dots,f(n)$ with weights $1/k^2$, which decrease strictly with $k$.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 8m21s
Problem
Let $f$ be an injective function from ${1,2,3,\ldots}$ in itself. Prove that for any $n$ we have: $\sum_{k=1}^{n} f(k)k^{-2} \geq \sum_{k=1}^{n} k^{-1}.$
Exploration
The expression involves a weighted sum of distinct positive integers $f(1),\dots,f(n)$ with weights $1/k^2$, which decrease strictly with $k$. The right-hand side depends only on the first $n$ harmonic terms, suggesting that the extremal configuration occurs when the values $f(k)$ are as small as possible and aligned with the largest weights.
A natural first step is to examine whether replacing any value $f(k)>n$ with a missing value in ${1,\dots,n}$ can only decrease the sum. This suggests that any minimizing configuration must use exactly the set ${1,\dots,n}$.
Once this reduction is made, the problem becomes an optimization over permutations of ${1,\dots,n}$ under decreasing weights. The structure suggests an exchange argument: if two values are out of order relative to the weights, swapping them reduces the sum.
The main risk lies in justifying that replacing a large value with a missing small value is always possible and strictly decreases the sum, and in ensuring that repeated exchanges eventually produce the identity arrangement without increasing the sum.
Problem Understanding
This is a Type C problem: it requires determining a lower bound for a weighted sum depending on an injective function $f:{1,2,3,\dots}\to{1,2,3,\dots}$.
For each fixed $n$, the goal is to show that among the values $f(1),\dots,f(n)$, which are distinct positive integers, the smallest possible value of the sum $\sum_{k=1}^n \frac{f(k)}{k^2}$ is $\sum_{k=1}^n \frac{1}{k}$.
The inequality is expected because the weights $1/k^2$ decrease with $k$, so placing smaller integers in positions with larger weights minimizes the sum. Injectivity prevents repetition, forcing competition among distinct integers and naturally aligning with ${1,\dots,n}$ in the optimal case.
The final statement is
$$\sum_{k=1}^{n} \frac{f(k)}{k^{2}} \geq \sum_{k=1}^{n} \frac{1}{k}.$$
Proof Architecture
Lemma 1 states that among all injective choices of $f(1),\dots,f(n)$, the minimum of $\sum_{k=1}^n \frac{f(k)}{k^2}$ is achieved when the set ${f(1),\dots,f(n)}$ equals ${1,\dots,n}$. The reason is that any value exceeding $n$ can be replaced by a missing smaller value without violating injectivity and strictly decreasing the sum.
Lemma 2 states that among all permutations of ${1,\dots,n}$, the minimum of $\sum_{k=1}^n \frac{f(k)}{k^2}$ occurs when $f(k)=k$ for all $k$. The reason is that swapping any inversion between larger assigned values and larger weights reduces the sum.
The hardest direction is Lemma 1, because it requires controlling the interaction between injectivity and replacement while preserving distinctness.
Solution
Lemma 1
Among all injective functions $f$ restricted to ${1,\dots,n}$, there exists a minimizing configuration in which ${f(1),\dots,f(n)}={1,\dots,n}$.
Proof. Consider any injective assignment $f(1),\dots,f(n)$ and define
$$S=\sum_{k=1}^n \frac{f(k)}{k^2}.$$
If the set ${f(1),\dots,f(n)}$ is not equal to ${1,\dots,n}$, then some integer $b\in{1,\dots,n}$ is not attained, while some value $a>n$ must appear among $f(1),\dots,f(n)$.
Choose indices $i$ and $j$ such that $f(i)=a$. Define a new function $g$ by $g(i)=b$ and $g(k)=f(k)$ for all $k\neq i$. Injectivity is preserved because $b$ was not previously in the image.
The change in the sum is
$$\sum_{k=1}^n \frac{g(k)}{k^2}-\sum_{k=1}^n \frac{f(k)}{k^2}=\frac{b-a}{i^2}.$$
Since $b<a$, this quantity is negative, so the sum strictly decreases. Any configuration containing a value exceeding $n$ therefore cannot minimize the expression, and repeated application of this replacement forces all values into ${1,\dots,n}$, completing the characterization.
Certification: this step establishes that any minimizer must use exactly the integers $1$ through $n$, and any attempt to include a larger value necessarily produces a strictly larger weighted sum.
Lemma 2
For any permutation $\sigma$ of ${1,\dots,n}$,
$$\sum_{k=1}^n \frac{\sigma(k)}{k^2} \geq \sum_{k=1}^n \frac{1}{k},$$
with equality when $\sigma(k)=k$.
Proof. Consider any permutation $\sigma$ that is not the identity. Then there exist indices $i<j$ such that $\sigma(i)>\sigma(j)$. Define a new permutation $\tau$ obtained by swapping the values at $i$ and $j$.
The change in the sum is
$$\left(\frac{\sigma(j)}{i^2}+\frac{\sigma(i)}{j^2}\right)-\left(\frac{\sigma(i)}{i^2}+\frac{\sigma(j)}{j^2}\right)$$
which simplifies to
$$(\sigma(i)-\sigma(j))\left(\frac{1}{j^2}-\frac{1}{i^2}\right).$$
Since $i<j$, we have $\frac{1}{j^2}<\frac{1}{i^2}$, and since $\sigma(i)>\sigma(j)$, the product is negative. Thus the swap strictly decreases the sum.
Repeated application of such swaps removes all inversions and leads to the identity permutation without increasing the sum at any step. Therefore the identity permutation minimizes the expression.
Certification: this step shows that any deviation from ordering values increasingly against decreasing weights produces a strictly larger sum, forcing the identity arrangement as the unique minimizer.
Completion of the argument
From Lemma 1, it suffices to consider permutations of ${1,\dots,n}$. From Lemma 2, the minimal permutation is the identity, yielding
$$\sum_{k=1}^n \frac{1}{k}.$$
Thus for every injective $f$,
$$\sum_{k=1}^{n} \frac{f(k)}{k^{2}} \geq \sum_{k=1}^{n} \frac{1}{k}.$$
This completes the proof. ∎
Verification of Key Steps
The crucial replacement argument in Lemma 1 depends on the existence of a missing element in ${1,\dots,n}$ whenever a value exceeds $n$. If injectivity were absent, this inference would fail because duplicates could mask missing values; injectivity is essential.
The exchange computation in Lemma 2 relies on factoring the difference into a product of a positive and a negative term. A careless sign reversal in the comparison of $i$ and $j$ would incorrectly suggest the swap increases the sum, reversing the conclusion.
The termination of successive swaps depends on the fact that each swap strictly reduces the sum while preserving finiteness of permutations; without strict decrease, cycles could not be excluded.
Alternative Approaches
A different approach uses a majorization argument: the vector $(f(1),\dots,f(n))$ under injectivity is minimized in the sense of convex ordering by $(1,\dots,n)$, and the weights $1/k^2$ form a decreasing sequence, allowing a direct application of a rearrangement principle.
Another approach interprets the inequality as an optimization over the symmetric group and applies induction on $n$, controlling the effect of inserting the element $n$ and comparing contributions before and after insertion.