48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

For convenience, define $a(0)=0$; then condition (1) persists for all pairs of nonnegative indices.

Lemma 1. For arbitrary nonnegative indices $n_1,\dots ,n_k$, we have $$a\left(\sum _{i=1}^k{n}_i\right)\le \sum _{i=1}^k{2}^{i}a\left(n_i\right)\text{\hspace{1em}(3)}$$ and $$a\left(\sum _{i=1}^k{n}_i\right)\le 2k\sum _{i=1}^{k}a\left(n_i\right).\text{\hspace{1em}(4)}$$ Proof. Inequality (3) is proved by induction on $k$. The base case $k=1$ is trivial, while the induction step is provided by $a\left({\sum }_{i=1}^{k+1}{n}_i\right)=a\left(n_1+{\sum }_{i=2}^{k+1}{n}_i\right)\le 2a\left(n_1\right)+2a\left({\sum }_{i=1}^k{n}_{i+1}\right)\le 2a\left(n_1\right)+2{\sum }_{i=1}^k{2}^{i}a\left(n_{i+1}\right)={\sum }_{i=1}^{k+1}{2}^{i}a\left(n_i\right)$.

To establish (4), first the inequality $$a\left(\sum _{i=1}^{2^d}{n}_i\right)\le 2^d\sum _{i=1}^{2^d}a\left(n_i\right)$$ can be proved by an obvious induction on $d$. Then, turning to (4), we find an integer $d$ such that $2^{d-1}<k\le 2^d$ to obtain $$a\left(\sum _{i=1}^k{n}_i\right)=a\left(\sum _{i=1}^k{n}_i+\sum _{i=k+1}^{2^d}0\right)\le 2^d\left(\sum _{i=1}^{k}a\left(n_i\right)+\sum _{i=k+1}^{2^d}a(0)\right)=2^d\sum _{i=1}^{k}a\left(n_i\right)\le 2k\sum _{i=1}^{k}a\left(n_i\right).$$

Fix an increasing unbounded sequence $0=M_0<M_1<M_2<\dots$ of real numbers; the exact values will be defined later. Let $n$ be an arbitrary positive integer and write $$n=\sum _{i=0}^d{\epsilon }_i\cdot 2^i,\text{ where }{\epsilon }_i\in \{0,1\}$$ Set ${\epsilon }_i=0$ for $i>d$, and take some positive integer $f$ such that $M_f>d$. Applying (3), we get $$a(n)=a\left(\sum _{k=1}^f\sum _{M_{k-1}\le i<M_k}{\epsilon }_i\cdot 2^i\right)\le \sum _{k=1}^f{2}^{k}a\left(\sum _{M_{k-1}\le i<M_k}{\epsilon }_i\cdot 2^i\right).$$ Note that there are less than $M_k-M_{k-1}+1$ integers in interval $\left[M_{k-1},M_k\right)$; hence, using (4) we have $$\begin{array}{rl}a(n)& \le \sum _{k=1}^f{2}^k\cdot 2\left(M_k-M_{k-1}+1\right)\sum _{M_{k-1}\le i<M_k}{\epsilon }_i\cdot a\left(2^i\right)\\ & \le \sum _{k=1}^f{2}^k\cdot 2{\left(M_k-M_{k-1}+1\right)}^2\underset{M_{k-1}\le i<M_k}{\max }a\left(2^i\right)\\ & \le \sum _{k=1}^f{2}^{k+1}{\left(M_k+1\right)}^2\cdot \frac{1}{{\left(M_{k-1}+1\right)}^c}=\sum _{k=1}^f{\left(\frac{M_k+1}{M_{k-1}+1}\right)}^2\frac{2^{k+1}}{{\left(M_{k-1}+1\right)}^{c-2}}\end{array}$$ Setting $M_k=4^{k/(c-2)}-1$, we obtain $$a(n)\le \sum _{k=1}^f{4}^{2/(c-2)}\frac{2^{k+1}}{{\left(4^{(k-1)/(c-2)}\right)}^{c-2}}=8\cdot 4^{2/(c-2)}\sum _{k=1}^f{\left(\frac{1}{2}\right)}^k<8\cdot 4^{2/(c-2)}$$ and the sequence $a(n)$ is bounded.

Solution 2:

Lemma 2. Suppose that $s_1,\dots ,s_k$ are positive integers such that $$\sum _{i=1}^k{2}^{-s_i}\le 1$$ Then for arbitrary positive integers $n_1,\dots ,n_k$ we have $$a\left(\sum _{i=1}^k{n}_i\right)\le \sum _{i=1}^k{2}^{s_i}a\left(n_i\right)$$ Proof. Apply an induction on $k$. The base cases are $k=1$ (trivial) and $k=2$ (follows from the condition (1)). Suppose that $k>2$. We can assume that $s_1\le s_2\le \cdots \le s_k$. Note that $$\sum _{i=1}^{k-1}{2}^{-s_i}\le 1-2^{-s_{k-1}}$$ since the left-hand side is a fraction with the denominator $2^{s_{k-1}}$, and this fraction is less than 1 . Define $s_{k-1}^{\prime }=s_{k-1}-1$ and $n_{k-1}^{\prime }=n_{k-1}+n_k$; then we have $$\sum _{i=1}^{k-2}{2}^{-s_i}+2^{-s_{k-1}^{\prime }}\le \left(1-2\cdot 2^{-s_{k-1}}\right)+2^{1-s_{k-1}}=1$$ Now, the induction hypothesis can be applied to achieve $$\begin{array}{rl}a\left(\sum _{i=1}^k{n}_i\right)=a\left(\sum _{i=1}^{k-2}{n}_i+n_{k-1}^{\prime }\right)& \le \sum _{i=1}^{k-2}{2}^{s_i}a\left(n_i\right)+2^{s_{k-1}^{\prime }}a\left(n_{k-1}^{\prime }\right)\\ & \le \sum _{i=1}^{k-2}{2}^{s_i}a\left(n_i\right)+2^{s_{k-1}-1}\cdot 2\left(a\left(n_{k-1}\right)+a\left(n_k\right)\right)\\ & \le \sum _{i=1}^{k-2}{2}^{s_i}a\left(n_i\right)+2^{s_{k-1}}a\left(n_{k-1}\right)+2^{s_k}a\left(n_k\right)\end{array}$$

Let $q=c/2>1$. Take an arbitrary positive integer $n$ and write $$n=\sum _{i=1}^k{2}^{u_i},0\le u_1<u_2<\cdots <u_k.$$ Choose $s_i=\lfloor {\log }_2{\left(u_i+1\right)}^q\rfloor +d(i=1,\dots ,k)$ for some integer $d$. We have $$\sum _{i=1}^k{2}^{-s_i}=2^{-d}\sum _{i=1}^k{2}^{-\lfloor {\log }_2{\left(u_i+1\right)}^q\rfloor },$$ and we choose $d$ in such a way that $$\frac{1}{2}<\sum _{i=1}^k{2}^{-s_i}\le 1$$ In particular, this implies $$2^d<2\sum _{i=1}^k{2}^{-\lfloor {\log }_2{\left(u_i+1\right)}^q\rfloor }<4\sum _{i=1}^k\frac{1}{{\left(u_i+1\right)}^q}.$$ Now, by Lemma 2 we obtain $$\begin{array}{rl}a(n)=a\left(\sum _{i=1}^k{2}^{u_i}\right)& \le \sum _{i=1}^k{2}^{s_i}a\left(2^{u_i}\right)\le \sum _{i=1}^k{2}^d{\left(u_i+1\right)}^q\cdot \frac{1}{{\left(u_i+1\right)}^{2q}}\\ & =2^d\sum _{i=1}^k\frac{1}{{\left(u_i+1\right)}^q}<4{\left(\sum _{i=1}^k\frac{1}{{\left(u_i+1\right)}^q}\right)}^2\end{array}$$ which is bounded since $q>1$.