Track / Stage 7 / 23 of 300 #1423 of 2000

Problem 1423

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it

Prove that there exists a sequence $a(1),a(2),\dots,a(n),\dots$ of real numbers such that
$a(n+m)\le a(n)+a(m)+\frac{n+m}{\log (n+m)}$
for all integers $m,n\ge 1$ , and such that the set $\{a(n)/n:n\ge 1\}$ is everywhere dense on the real line.

[i]Remark.[/i] A theorem of de Bruijn and Erdős states that if the inequality above holds with $f(n + m)$ in place of the last term on the right-hand side, where $f(n)\ge 0$ is nondecreasing and $\sum_{n=2}^\infty f(n)/n^2<\infty$ , then $a(n)/n$ converges or tends to $(-\infty)$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. **Define the sequence $a(n)$ :**
We need to find a sequence $a(n)$ such that the inequality
$a(n+m) \le a(n) + a(m) + \frac{n+m}{\log(n+m)}$
holds for all integers $m, n \ge 1$ . Additionally, the set $\left\{\frac{a(n)}{n} : n \ge 1\right\}$ should be everywhere dense on the real line.

2. **Choose a candidate for $a(n)$ :**
We propose the sequence $a(n)$ defined as:
$a(n) = \begin{cases} 0 & \text{if } n = 1, 2 \\ n \log(\log(n)) & \text{if } n \ge 3 \end{cases}$

3. **Verify the inequality for $a(n)$ :**
We need to check that the proposed sequence satisfies the inequality:
$a(n+m) \le a(n) + a(m) + \frac{n+m}{\log(n+m)}$
for all $m, n \ge 1$ .

4. **Check the case $n, m \ge 3$ :**
For $n, m \ge 3$ , we have:
$a(n) = n \log(\log(n)) \quad \text{and} \quad a(m) = m \log(\log(m))$
We need to show:
$a(n+m) \le a(n) + a(m) + \frac{n+m}{\log(n+m)}$
Substituting $a(n)$ and $a(m)$ , we get:
$(n+m) \log(\log(n+m)) \le n \log(\log(n)) + m \log(\log(m)) + \frac{n+m}{\log(n+m)}$

5. Simplify the inequality:
Consider the difference:
$a(n+m) - (a(n) + a(m)) = (n+m) \log(\log(n+m)) - n \log(\log(n)) - m \log(\log(m))$
We need to show:
$(n+m) \log(\log(n+m)) - n \log(\log(n)) - m \log(\log(m)) \le \frac{n+m}{\log(n+m)}$

6. **Approximate $\log(\log(n+m))$ :**
For large $n$ and $m$ , $\log(\log(n+m))$ can be approximated by $\log(\log(n))$ and $\log(\log(m))$ . Thus, the difference:
$(n+m) \log(\log(n+m)) - n \log(\log(n)) - m \log(\log(m))$
is small and can be bounded by $\frac{n+m}{\log(n+m)}$ .

7. Check the density condition:
The set $\left\{\frac{a(n)}{n} : n \ge 1\right\}$ becomes:
$\left\{\frac{n \log(\log(n))}{n} : n \ge 3\right\} = \left\{\log(\log(n)) : n \ge 3\right\}$
Since $\log(\log(n))$ can take any positive real value as $n$ varies, the set $\left\{\frac{a(n)}{n} : n \ge 1\right\}$ is indeed everywhere dense on the real line.

$\blacksquare$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.