Olimpiade Italiana di Matematica

Solution:

The statement is true. To prove this, let us first indicate a possible strategy.
Fixing a sequence of integers $0<n_{1}<n_{2}<\ldots$, we divide the indices into disjoint intervals: the first interval comprises the indices $1, \ldots, n_{1}$, the second the indices $n_{1}+1, \ldots, n_{2}$, the third the indices $n_{2}+1, \ldots, n_{3}$, and so on. Let us now set $a_{i}=x_{i}$ if $i$ belongs to an even interval (second, fourth, ..), and $a_{i}=0$ otherwise; symmetrically, let us set $b_{i}=x_{i}$ if $i$ belongs to an odd interval and $b_{i}=0$ otherwise. In this way it is evident that for every $n$ one of $a_{n}$ and $b_{n}$ coincides with $x_{n}$, while the other equals zero, and therefore $x_{n}=a_{n}+b_{n}$ for every $n$. Let us now show that, by choosing the sequence $0<n_{1}<n_{2}<\ldots$ appropriately, one can arrange that there are infinitely many values of $n$ for which $a_{1}+\ldots+a_{n} \leq n$ and infinitely many values of $n$ for which $b_{1}+\ldots+b_{n} \leq n$.
Let us set $n_{1}=1$: consequently the first interval consists of the single index 1 and therefore $b_{1}=x_{1}, a_{1}=0$. In particular the first inequality $\left(a_{n_{1}} \leq n_{1}\right)$ is satisfied.
We now want to choose $n_{2}$ so as to satisfy the second inequality $\left(b_{1}+b_{2}+\ldots+b_{n_{2}} \leq n_{2}\right)$. To this end, note that from 2 to $n_{2}$ we are in the second interval of indices, and thus all the corresponding $b_{i}$ are zero: the second inequality therefore reduces to $b_{1} \leq n_{2}$ and will thus be satisfied provided we take an $n_{2}$ large enough (we can, for example, take the smallest integer greater than $n_{1}=1$ and than $b_{1}$).
Let us now move on to choosing $n_{3}$ so as to satisfy the third inequality $\left(a_{1}+a_{2}+\ldots+a_{n_{3}} \leq n_{3}\right)$. To this end, note that from $n_{2}+1$ to $n_{3}$ we are in the third interval of indices, and thus all the corresponding $a_{i}$ are zero: the third inequality therefore reduces to $a_{1}+a_{2}+\ldots+a_{n_{2}} \leq n_{3}$, an expression in which $n_{3}$ appears only on the right-hand side, and which will therefore be satisfied provided we take $n_{3}$ large enough (we can, for example, take the smallest integer greater than $n_{2}$ and than $a_{1}+a_{2}+\ldots+a_{n_{2}}$).
We proceed analogously to choose $n_{4}, n_{5}, \ldots$
This type of construction can be carried forward recursively. We give here a mathematically rigorous version of the idea presented above.
Proof of the statement. Given any sequence of numbers greater than or equal to zero $x_{1}, x_{2}, x_{3}, \ldots$, let us define a sequence of integers $0<n_{1}<n_{2}<n_{3}<\ldots$ and the sequences $a_{1}, a_{2}, a_{3} \ldots, b_{1}, b_{2}, b_{3} \ldots$ as follows.
- $n_{1}=1, a_{1}=0, b_{1}=x_{1}$
- we define $n_{2}$ as the smallest integer greater than $n_{1}=1$ such that $b_{1}=x_{1} \leq n_{2}$; for $i=2, \ldots n_{2}$ we set $a_{i}=x_{i}, b_{i}=0$.
Let us now suppose that we have defined $n_{1}, \ldots, n_{k}$ and $a_{i}, b_{i}$ for $i=1, \ldots n_{k}$.
- if $k=2 h$ is even, we define $n_{2 h+1}$ as the smallest positive integer greater than $n_{2 h}$ such that $a_{1}+\cdots+a_{2 h} \leq n_{2 h+1}$; for $i=n_{2 h}+1, \ldots, n_{2 h+1}$ we set $a_{i}=0, b_{i}=x_{i}$;
- if $k=2 h+1$ is odd, we define $n_{2 h+2}$ as the smallest positive integer greater than $n_{2 h+1}$ such that $b_{1}+\cdots+b_{2 h+1} \leq n_{2 h+2}$; for $i=n_{2 h+1}+1, \ldots, n_{2 h+2}$ we set $a_{i}=x_{i}, b_{i}=0$.
From the construction it is clear that $a_{i}+b_{i}=x_{i}$ for every $i$ and that
$$\begin{aligned} a_{1}+\cdots+a_{n_{k}} \leq n_{k} & \text{ if } k \text{ is odd; } \\ b_{1}+\cdots+b_{n_{k}} \leq n_{k} & \text{ if } k \text{ is even. } \end{aligned}$$