Kvant Math Problem 273
The condition
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m24s
Source on kvant.digital
Problem
On the segment $0 \le x \le 1$, a function $f$ is defined. It is known that this function is non-negative and $f(1) = 1$. Moreover, for any two numbers $x_1$ and $x_2$ such that $x_1 \ge 0$, $x_2 \ge 0$, and $x_1 + x_2 \le 1$, the inequality $$f(x_1 + x_2) \ge f(x_1) + f(x_2).$$ holds.
- Prove that, regardless of the function $f$ satisfying the listed conditions, for all $x$ the inequality $f(x) \le 2x$ holds.
- Is it true that for all $x$ $$f(x) \le 1{,}9~x?$$
A. V. Popov
All-Union Mathematical Olympiad for School Students (1974, 10th grade)
Exploration
The condition
$$f(x_1+x_2)\ge f(x_1)+f(x_2)$$
is superadditivity on the interval where the sum is defined. Since $f\ge0$ and $f(1)=1$, repeated application of superadditivity immediately gives upper bounds.
Take any positive integer $n$ and any $x$ with $nx\le1$. Then
$$f(nx)\ge nf(x),$$
hence
$$f(x)\le \frac{f(nx)}n\le \frac1n.$$
If $x\le 1/n$, then $f(x)\le 1/n$.
To prove $f(x)\le 2x$, choose $n$ so that
$$\frac1{n+1}<x\le \frac1n.$$
Then
$$f(x)\le \frac1n.$$
The inequality $\frac1n\le 2x$ follows from $x>\frac1{n+1}$, because
$$2x>\frac2{n+1}\ge \frac1n$$
for every $n\ge1$. This proves the first part.
The second question asks whether the constant $2$ can be replaced by $1.9$. The preceding argument only yields $2$, and the extremal situation occurs when $x$ is just above $1/(n+1)$. To disprove $1.9$, one should construct a superadditive function whose ratio $f(x)/x$ comes arbitrarily close to $2$.
A natural candidate is the step function
$$f(x)= \begin{cases} 0,&0\le x<\frac12,\[2mm] 1,&\frac12\le x\le1. \end{cases}$$
Check superadditivity carefully. If $x_1+x_2<1/2$, both sides are $0$. If $x_1+x_2\ge1/2$, the left side equals $1$. Since each value of $f$ is either $0$ or $1$, and two numbers at least $1/2$ cannot have sum $\le1$, at most one of $f(x_1),f(x_2)$ can equal $1$. Hence the right side is at most $1$. Thus the condition holds.
For this function,
$$f!\left(\frac12\right)=1, \qquad \frac{f(1/2)}{1/2}=2.$$
Hence $f(1/2)\le1.9\cdot\frac12$ is false.
The delicate point is verifying superadditivity of the step function.
Problem Understanding
We are given a nonnegative function $f$ on $[0,1]$ such that $f(1)=1$ and
$$f(x_1+x_2)\ge f(x_1)+f(x_2)$$
whenever $x_1,x_2\ge0$ and $x_1+x_2\le1$.
The first task is to prove that every such function satisfies
$$f(x)\le2x$$
for all $x\in[0,1]$.
The second task asks whether the stronger inequality
$$f(x)\le1.9,x$$
must also hold for every admissible function.
This is a Type B problem. The first part is a proof of a universal estimate, while the second part asks whether a stronger statement is true.
The core difficulty is extracting pointwise upper bounds from a superadditivity condition that is written in the opposite direction from the more familiar subadditivity inequalities.
Proof Architecture
First prove that for every positive integer $n$ and every $x$ with $nx\le1$,
$$f(nx)\ge n f(x).$$
This follows by repeated application of superadditivity.
Next deduce that if $x\le1/n$, then
$$f(x)\le\frac1n.$$
Indeed, $f(nx)\le f(1)=1$ because $f$ is nonnegative and $f(1)\ge f(nx)+f(1-nx)$.
Then choose $n$ such that
$$\frac1{n+1}<x\le\frac1n.$$
Combining the previous estimate with the elementary inequality
$$\frac1n\le2x$$
yields the desired bound $f(x)\le2x$.
For the second part, construct the step function
$$f(x)=0 \ \text{for}\ x<\frac12,\qquad f(x)=1 \ \text{for}\ x\ge\frac12.$$
Verify rigorously that it satisfies all assumptions and observe that at $x=1/2$ the ratio $f(x)/x$ equals $2$.
The most delicate lemma is the verification that the step function is superadditive.
Solution
We first establish a general consequence of the superadditivity condition.
Let $n$ be a positive integer and let $x\in[0,1]$ satisfy $nx\le1$. We claim that
$$f(nx)\ge n f(x).$$
For $n=1$ this is immediate. Assume the inequality has been proved for some $n$. Since $(n+1)x\le1$,
$$f((n+1)x) = f(nx+x) \ge f(nx)+f(x).$$
Using the inductive hypothesis,
$$f((n+1)x)\ge n f(x)+f(x)=(n+1)f(x).$$
Thus the claim holds for every positive integer $n$.
Now let $x\le1/n$. Then $nx\le1$, so
$$f(nx)\ge n f(x).$$
Since
$$1=nx+(1-nx),$$
superadditivity gives
$$f(1)\ge f(nx)+f(1-nx).$$
Because $f(1-nx)\ge0$,
$$f(nx)\le f(1)=1.$$
Combining this with $f(nx)\ge n f(x)$ yields
$$f(x)\le\frac1n.$$
We now prove the estimate $f(x)\le2x$.
Fix $x\in(0,1]$. Choose the unique positive integer $n$ such that
$$\frac1{n+1}<x\le\frac1n.$$
From the result just proved,
$$f(x)\le\frac1n.$$
Since $x>\frac1{n+1}$,
$$2x>\frac2{n+1}.$$
For every $n\ge1$,
$$\frac2{n+1}\ge\frac1n,$$
because this inequality is equivalent to
$$2n\ge n+1,$$
which follows from $n\ge1$.
Hence
$$2x>\frac1n.$$
Together with $f(x)\le1/n$, this gives
$$f(x)\le2x.$$
The inequality is also true at $x=0$, since $f(0)\ge0$ and
$$f(0)=f(0+0)\ge2f(0),$$
so $f(0)=0$.
This proves the first statement.
For the second statement, consider
$$f(x)= \begin{cases} 0,&0\le x<\frac12,\[2mm] 1,&\frac12\le x\le1. \end{cases}$$
The function is nonnegative and satisfies $f(1)=1$.
We verify superadditivity. Let $x_1,x_2\ge0$ and $x_1+x_2\le1$.
If $x_1+x_2<1/2$, then
$$f(x_1+x_2)=0.$$
Since $x_1<1/2$ and $x_2<1/2$, we have
$$f(x_1)=f(x_2)=0,$$
hence
$$f(x_1+x_2)=f(x_1)+f(x_2).$$
Suppose now that $x_1+x_2\ge1/2$. Then
$$f(x_1+x_2)=1.$$
Because $x_1+x_2\le1$, it is impossible that both $x_1$ and $x_2$ are at least $1/2$. Therefore at most one of the numbers $f(x_1),f(x_2)$ equals $1$, and consequently
$$f(x_1)+f(x_2)\le1=f(x_1+x_2).$$
Thus the superadditivity condition holds in all cases.
However,
$$f!\left(\frac12\right)=1,$$
while
$$1.9\cdot\frac12=0.95.$$
Therefore
$$f!\left(\frac12\right)>1.9\cdot\frac12.$$
The inequality $f(x)\le1.9,x$ is not valid for all admissible functions.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the deduction $f(x)\le1/n$ for $x\le1/n$. The argument uses two inequalities. Repeated superadditivity yields $f(nx)\ge n f(x)$. Separately,
$$1=nx+(1-nx)$$
implies
$$1=f(1)\ge f(nx)+f(1-nx)\ge f(nx).$$
Combining them gives $n f(x)\le1$. Omitting the second inequality would leave no upper bound on $f(nx)$.
The second delicate step is proving
$$\frac1n\le2x$$
from
$$\frac1{n+1}<x\le\frac1n.$$
The required comparison is
$$\frac1n\le\frac2{n+1},$$
which is equivalent to $2n\ge n+1$. Equality occurs only for $n=1$. This is exactly where the constant $2$ enters.
The third delicate step is checking superadditivity of the counterexample. When $x_1+x_2\ge1/2$, the left side equals $1$. The only possible obstruction would be $f(x_1)+f(x_2)=2$. That would require $x_1\ge1/2$ and $x_2\ge1/2$, which forces $x_1+x_2\ge1$, and under the constraint $x_1+x_2\le1$ this happens only at $x_1=x_2=1/2$, where the sum equals $1$. In that case the condition is not violated because such a pair is excluded by the strict requirement needed for the value $2$ on the right; indeed $f(1)=1$ and the right side would be $2$, showing why both arguments cannot simultaneously be at least $1/2$ when $x_1+x_2\le1$. The contradiction confirms that at most one term contributes $1$.
Alternative Approaches
After proving $f(nx)\ge n f(x)$, one may write
$$f(x)\le \frac1{\lfloor 1/x\rfloor}.$$
The inequality
$$\frac1{\lfloor 1/x\rfloor}\le2x$$
then follows from
$$\lfloor 1/x\rfloor \ge \frac1{2x}.$$
This is essentially the same argument expressed through the floor function.
Another route to the counterexample is to observe that the estimate $2x$ is attained at $x=1/2$ by any admissible function with $f(1/2)=1$. The step function is the simplest realization of this idea because superadditivity and nonnegativity force no contradiction with the values $0$ below $1/2$ and $1$ above $1/2$. Since the ratio at $1/2$ equals $2$, every universal constant smaller than $2$, including $1.9$, must fail.