Maths Olympiad Prep

Library / /270 of 383

, 2011

Algebra Difficulty 8.8 Shortlist Prove it IMO

Determine all sequences (x1,x2,,x2011)\left(x_{1}, x_{2}, \ldots, x_{2011}\right) of positive integers such that for every positive integer nn there is an integer aa with
x1n+2x2n++2011x2011n=an+1+1. x_{1}^{n}+2 x_{2}^{n}+\cdots+2011 x_{2011}^{n}=a^{n+1}+1 .

Solution

Throughout this solution, the set of positive integers will be denoted by Z+\mathbb{Z}_{+}.
Put k=2+3++2011=2023065k=2+3+\cdots+2011=2023065. We have
1n+2kn+2011kn=1+kkn=kn+1+1 1^{n}+2 k^{n}+\cdots 2011 k^{n}=1+k \cdot k^{n}=k^{n+1}+1
for all nn, so (1,k,,k)(1, k, \ldots, k) is a valid sequence. We shall prove that it is the only one.
Let a valid sequence (x1,,x2011)\left(x_{1}, \ldots, x_{2011}\right) be given. For each nZ+n \in \mathbb{Z}_{+} we have some ynZ+y_{n} \in \mathbb{Z}_{+} with
x1n+2x2n++2011x2011n=ynn+1+1. x_{1}^{n}+2 x_{2}^{n}+\cdots+2011 x_{2011}^{n}=y_{n}^{n+1}+1 .
Note that x1n+2x2n++2011x2011n<(x1+2x2++2011x2011)n+1x_{1}^{n}+2 x_{2}^{n}+\cdots+2011 x_{2011}^{n}<\left(x_{1}+2 x_{2}+\cdots+2011 x_{2011}\right)^{n+1}, which implies that the sequence (yn)\left(y_{n}\right) is bounded. In particular, there is some yZ+y \in \mathbb{Z}_{+} with yn=yy_{n}=y for infinitely many nn.
Let mm be the maximum of all the xix_{i}. Grouping terms with equal xix_{i} together, the sum x1n+2x2n++2011x2011nx_{1}^{n}+ 2 x_{2}^{n}+\cdots+2011 x_{2011}^{n} can be written as
x1n+2x2n++x2011n=ammn+am1(m1)n++a1 x_{1}^{n}+2 x_{2}^{n}+\cdots+x_{2011}^{n}=a_{m} m^{n}+a_{m-1}(m-1)^{n}+\cdots+a_{1}
with ai0a_{i} \geq 0 for all ii and a1++am=1+2++2011a_{1}+\cdots+a_{m}=1+2+\cdots+2011. So there exist arbitrarily large values of nn, for which
ammn++a11yyn=0. \begin{equation*} a_{m} m^{n}+\cdots+a_{1}-1-y \cdot y^{n}=0 . \tag{1} \end{equation*}
The following lemma will help us to determine the aia_{i} and yy :
Lemma. Let integers b1,,bNb_{1}, \ldots, b_{N} be given and assume that there are arbitrarily large positive integers nn with b1+b22n++bNNn=0b_{1}+b_{2} 2^{n}+\cdots+b_{N} N^{n}=0. Then bi=0b_{i}=0 for all ii.
Proof. Suppose that not all bib_{i} are zero. We may assume without loss of generality that bN0b_{N} \neq 0.
Dividing through by NnN^{n} gives
bN=bN1(N1N)n++b1(1N)n(bN1++b1)(N1N)n. \left|b_{N}\right|=\left|b_{N-1}\left(\frac{N-1}{N}\right)^{n}+\cdots+b_{1}\left(\frac{1}{N}\right)^{n}\right| \leq\left(\left|b_{N-1}\right|+\cdots+\left|b_{1}\right|\right)\left(\frac{N-1}{N}\right)^{n} .
The expression (N1N)n\left(\frac{N-1}{N}\right)^{n} can be made arbitrarily small for nn large enough, contradicting the assumption that bNb_{N} be non-zero. \square
We obviously have y>1y>1. Applying the lemma to (1) we see that am=y=m,a1=1a_{m}=y=m, a_{1}=1, and all the other aia_{i} are zero. This implies (x1,,x2011)=(1,m,,m)\left(x_{1}, \ldots, x_{2011}\right)=(1, m, \ldots, m). But we also have 1+m=a1++am=1++2011=1+k1+m=a_{1}+\cdots+a_{m}=1+\cdots+2011=1+k so m=km=k, which is what we wanted to show.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.