Kvant Math Problem 571

The condition gives control only on a sparse subsequence of the sequence, namely the indices $1,4,9,\dots,n^2$, and the weights are harmonic in $k$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m59s
Source on kvant.digital

Problem

A decreasing sequence $(x_n)$ of positive numbers is such that for any natural number $n$ $$\dfrac{x_1}1+\dfrac{x_4}2+\dfrac{x_9}3+\ldots+\dfrac{x_{n^2}}n\le1.$$ Prove that for any natural number $n$ $$\dfrac{x_1}1+\dfrac{x_2}2+\dfrac{x_3}3+\ldots+\dfrac{x_n}n\lt3.$$

Z. Chanturia

All-Union Mathematical Olympiad of School Students (1979, 10th grade)

Exploration

The condition gives control only on a sparse subsequence of the sequence, namely the indices $1,4,9,\dots,n^2$, and the weights are harmonic in $k$. Because $(x_n)$ is decreasing, values between consecutive squares are dominated by the value at the left endpoint of the block.

A natural strategy is to partition the sum $\sum_{i=1}^n \frac{x_i}{i}$ into blocks of the form $i\in[k^2,(k+1)^2-1]$. Within each block, all terms $x_i$ are bounded above by $x_{k^2}$, which allows reduction of the problem to bounding purely harmonic sums over square intervals.

The key difficulty is to compare the harmonic mass of each square block with the weight $\frac{1}{k}$ appearing in the hypothesis. If each block contributes at most $\frac{3x_{k^2}}{k}$, then the hypothesis immediately yields the desired global bound. The central task is therefore a uniform estimate on

$\sum_{i=k^2}^{(k+1)^2-1}\frac{1}{i}.$

The most delicate point is ensuring that this bound scales exactly like $1/k$, since the hypothesis involves $\frac{x_{k^2}}{k}$ rather than $\frac{x_{k^2}}{k^2}$.

Problem Understanding

This is a Type B problem: prove a uniform upper bound on a weighted harmonic sum under a square-index constraint.

We are given a decreasing sequence of positive numbers such that for every natural $n$,

$\frac{x_1}{1}+\frac{x_4}{2}+\cdots+\frac{x_{n^2}}{n}\le 1.$

We must prove that for every $n$,

$\sum_{i=1}^n \frac{x_i}{i}<3.$

The core difficulty is transferring control from sparse square indices to all indices while respecting harmonic weights. The expected mechanism is block decomposition by squares and domination using monotonicity.

The desired conclusion is

$\boxed{<3}.$

Proof Architecture

Let $S_n=\sum_{i=1}^n \frac{x_i}{i}$. The proof will rely on the following steps.

First, the interval ${1,2,\dots,n}$ is partitioned into blocks ${k^2,\dots,(k+1)^2-1}$.

Second, for each block, one shows the monotonicity bound $x_i\le x_{k^2}$.

Third, one proves the harmonic estimate

$\sum_{i=k^2}^{(k+1)^2-1}\frac{1}{i}\le \frac{3}{k}.$

Fourth, these two bounds combine to give

$S_n\le \sum_{k\le \sqrt n} x_{k^2}\cdot \frac{3}{k}.$

Fifth, the given hypothesis implies

$\sum_{k\le \sqrt n} \frac{x_{k^2}}{k}\le 1,$

which yields the final inequality.

The hardest point is the uniform bound on the harmonic sums over square intervals.

Solution

For each natural $k$, consider the block of indices

$B_k={k^2,k^2+1,\dots,(k+1)^2-1}.$

These blocks are disjoint and cover all positive integers.

Let $n$ be fixed and let $m=\lfloor \sqrt n\rfloor$. Then every index $i\le n$ belongs either to a complete block $B_k$ with $k\le m$ or to a partial final segment inside $B_{m+1}$. Since all terms are positive, extending to a full block only increases the sum, hence

$\sum_{i=1}^n \frac{x_i}{i}\le \sum_{k=1}^{m+1}\sum_{i\in B_k}\frac{x_i}{i}.$

Fix a block $B_k$. For every $i\in B_k$, the inequality $i\ge k^2$ holds, hence $\frac{1}{i}\le \frac{1}{k^2}$. Since the sequence $(x_n)$ is decreasing and $i\ge k^2$, one has $x_i\le x_{k^2}$ for all $i\in B_k$. Therefore

$\sum_{i\in B_k}\frac{x_i}{i}\le x_{k^2}\sum_{i=k^2}^{(k+1)^2-1}\frac{1}{i}\le x_{k^2}\cdot \frac{2k+1}{k^2}.$

The quantity $\frac{2k+1}{k^2}$ satisfies

$\frac{2k+1}{k^2}=\frac{2}{k}+\frac{1}{k^2}\le \frac{3}{k}.$

Thus

$\sum_{i\in B_k}\frac{x_i}{i}\le \frac{3x_{k^2}}{k}.$

Summing over all blocks yields

$\sum_{i=1}^n \frac{x_i}{i}\le \sum_{k=1}^{m+1}\frac{3x_{k^2}}{k}=3\sum_{k=1}^{m+1}\frac{x_{k^2}}{k}.$

The hypothesis applied with $n=m+1$ gives

$\sum_{k=1}^{m+1}\frac{x_{k^2}}{k}\le 1,$

hence

$\sum_{i=1}^n \frac{x_i}{i}\le 3.$

Since each block estimate is strict for at least one index (the inequality $\frac{1}{i}<\frac{1}{k^2}$ holds for $i>k^2$), the final inequality is strict:

$\sum_{i=1}^n \frac{x_i}{i}<3.$

This completes the proof. ∎

Verification of Key Steps

The first delicate point is the passage from the original sum to blockwise sums. Each integer $i$ lies in exactly one interval $B_k$, so no overlap occurs, and replacing the truncated last block by a full block can only increase the sum since all terms are positive.

The second point is the uniform harmonic bound. For $i\in B_k$, the inequalities $k^2\le i\le (k+1)^2-1$ imply $\frac{1}{i}\le \frac{1}{k^2}$ and the number of terms equals $(k+1)^2-k^2=2k+1$, which gives the exact estimate

$\sum_{i=k^2}^{(k+1)^2-1}\frac{1}{i}\le \frac{2k+1}{k^2}.$

The third point is compatibility with the hypothesis. The block decomposition produces the sum $\sum \frac{x_{k^2}}{k}$ with the same indexing and range as in the assumption, so the given inequality applies directly without reindexing loss.

Alternative Approaches

A different approach replaces the crude bound on each block by an integral comparison, estimating

$\sum_{i=k^2}^{(k+1)^2-1}\frac{1}{i}$

via logarithmic integrals and then relating the result to $\frac{1}{k}$. This leads to a sharper constant than $3$, but requires more delicate control of logarithmic differences.

The present argument is preferable because it avoids analytic estimates and reduces the problem to a purely combinatorial counting bound, where both the number of terms in each block and their maximal size are explicitly controlled.