Maths Olympiad Prep

Library / /33 of 36

Algebra Difficulty 7.5 National Olympiad, round 2 Prove it Italy

Problem:

Determine whether the following statement is true or false:
"For every sequence x1,x2,x3,x_{1}, x_{2}, x_{3}, \ldots of real numbers greater than or equal to zero there exist two sequences a1,a2,a3,a_{1}, a_{2}, a_{3}, \ldots and b1,b2,b3,b_{1}, b_{2}, b_{3}, \ldots of real numbers greater than or equal to zero such that
- xn=an+bnx_{n}=a_{n}+b_{n} for every nn;
- a1++anna_{1}+\ldots+a_{n} \leq n for infinitely many values of nn;
- b1++bnnb_{1}+\ldots+b_{n} \leq n for infinitely many values of nn, possibly different from the previous ones."

Solution

Solution:

The statement is true. To prove this, let us first indicate a possible strategy.
Fixing a sequence of integers 0<n1<n2<0<n_{1}<n_{2}<\ldots, we divide the indices into disjoint intervals: the first interval comprises the indices 1,,n11, \ldots, n_{1}, the second the indices n1+1,,n2n_{1}+1, \ldots, n_{2}, the third the indices n2+1,,n3n_{2}+1, \ldots, n_{3}, and so on. Let us now set ai=xia_{i}=x_{i} if ii belongs to an even interval (second, fourth, ..), and ai=0a_{i}=0 otherwise; symmetrically, let us set bi=xib_{i}=x_{i} if ii belongs to an odd interval and bi=0b_{i}=0 otherwise. In this way it is evident that for every nn one of ana_{n} and bnb_{n} coincides with xnx_{n}, while the other equals zero, and therefore xn=an+bnx_{n}=a_{n}+b_{n} for every nn. Let us now show that, by choosing the sequence 0<n1<n2<0<n_{1}<n_{2}<\ldots appropriately, one can arrange that there are infinitely many values of nn for which a1++anna_{1}+\ldots+a_{n} \leq n and infinitely many values of nn for which b1++bnnb_{1}+\ldots+b_{n} \leq n.
Let us set n1=1n_{1}=1: consequently the first interval consists of the single index 1 and therefore b1=x1,a1=0b_{1}=x_{1}, a_{1}=0. In particular the first inequality (an1n1)\left(a_{n_{1}} \leq n_{1}\right) is satisfied.
We now want to choose n2n_{2} so as to satisfy the second inequality (b1+b2++bn2n2)\left(b_{1}+b_{2}+\ldots+b_{n_{2}} \leq n_{2}\right). To this end, note that from 2 to n2n_{2} we are in the second interval of indices, and thus all the corresponding bib_{i} are zero: the second inequality therefore reduces to b1n2b_{1} \leq n_{2} and will thus be satisfied provided we take an n2n_{2} large enough (we can, for example, take the smallest integer greater than n1=1n_{1}=1 and than b1b_{1}).
Let us now move on to choosing n3n_{3} so as to satisfy the third inequality (a1+a2++an3n3)\left(a_{1}+a_{2}+\ldots+a_{n_{3}} \leq n_{3}\right). To this end, note that from n2+1n_{2}+1 to n3n_{3} we are in the third interval of indices, and thus all the corresponding aia_{i} are zero: the third inequality therefore reduces to a1+a2++an2n3a_{1}+a_{2}+\ldots+a_{n_{2}} \leq n_{3}, an expression in which n3n_{3} appears only on the right-hand side, and which will therefore be satisfied provided we take n3n_{3} large enough (we can, for example, take the smallest integer greater than n2n_{2} and than a1+a2++an2a_{1}+a_{2}+\ldots+a_{n_{2}}).
We proceed analogously to choose n4,n5,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 x1,x2,x3,x_{1}, x_{2}, x_{3}, \ldots, let us define a sequence of integers 0<n1<n2<n3<0<n_{1}<n_{2}<n_{3}<\ldots and the sequences a1,a2,a3,b1,b2,b3a_{1}, a_{2}, a_{3} \ldots, b_{1}, b_{2}, b_{3} \ldots as follows.
- n1=1,a1=0,b1=x1n_{1}=1, a_{1}=0, b_{1}=x_{1}
- we define n2n_{2} as the smallest integer greater than n1=1n_{1}=1 such that b1=x1n2b_{1}=x_{1} \leq n_{2}; for i=2,n2i=2, \ldots n_{2} we set ai=xi,bi=0a_{i}=x_{i}, b_{i}=0.
Let us now suppose that we have defined n1,,nkn_{1}, \ldots, n_{k} and ai,bia_{i}, b_{i} for i=1,nki=1, \ldots n_{k}.
- if k=2hk=2 h is even, we define n2h+1n_{2 h+1} as the smallest positive integer greater than n2hn_{2 h} such that a1++a2hn2h+1a_{1}+\cdots+a_{2 h} \leq n_{2 h+1}; for i=n2h+1,,n2h+1i=n_{2 h}+1, \ldots, n_{2 h+1} we set ai=0,bi=xia_{i}=0, b_{i}=x_{i};
- if k=2h+1k=2 h+1 is odd, we define n2h+2n_{2 h+2} as the smallest positive integer greater than n2h+1n_{2 h+1} such that b1++b2h+1n2h+2b_{1}+\cdots+b_{2 h+1} \leq n_{2 h+2}; for i=n2h+1+1,,n2h+2i=n_{2 h+1}+1, \ldots, n_{2 h+2} we set ai=xi,bi=0a_{i}=x_{i}, b_{i}=0.
From the construction it is clear that ai+bi=xia_{i}+b_{i}=x_{i} for every ii and that
a1++anknk if k is odd; b1++bnknk if k is even.  \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}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.