Maths Olympiad Prep

Library / /183 of 397

Algebra Difficulty 5.7 AIME, harder Prove it Taiwan

Determine all sequences of positive integers {x1,x2,,x101}\{x_1, x_2, \dots, x_{101}\} such that for every positive integer nn there exists an integer aa satisfying
x1n+2x2n++101x101n=an+1+1. x_1^n + 2x_2^n + \dots + 101x_{101}^n = a^{n+1} + 1.

Solution

The unique sequence satisfying the problem is
{x1,x2,,x101}=(1,k,,k) where k=2+3++101=5150. \{x_1, x_2, \dots, x_{101}\} = (1, k, \dots, k) \text{ where } k = 2 + 3 + \dots + 101 = 5150.
Let NN denote the set of all positive integers. k=2+3++101=5150k = 2 + 3 + \dots + 101 = 5150. Then we obtain
1n+2kn++101kn=1+(2+3++101)kn=1+kkn=kn+1+11^n + 2k^n + \dots + 101k^n = 1 + (2+3+\dots+101)k^n = 1 + k \cdot k^n = k^{n+1} + 1
for any nn, so (1,k,,k)(1, k, \dots, k) satisfies the problem. Below we prove that this solution is unique.

Let (x1,,x101)(x_1, \dots, x_{101}) satisfy the problem. Then for any nNn \in N, there exists ynNy_n \in N such that
x1n+2x2n++101x101n=ynn+1+1. x_1^n + 2x_2^n + \cdots + 101x_{101}^n = y_n^{n+1} + 1.
Note that x1n+2x2n++101x101n<(x1n+2x2++101x101)n+1x_1^n + 2x_2^n + \dots + 101x_{101}^n < (x_1^n + 2x_2 + \dots + 101x_{101})^{n+1}, from which it can be deduced that the sequence {yn}\{y_n\} is a bounded sequence. That is, there exists yNy \in N such that yn=y,nn0y_n = y, n \ge n_0.

Let m=max{xi1i101}m = \max\{x_i|1 \le i \le 101\}. Then x1n+2x2n++101x101nx_1^n + 2x_2^n + \dots + 101x_{101}^n can be rewritten as follows
x1n+2x2n++101x101n=ammn+am1(m1)n++a1 x_1^n + 2x_2^n + \cdots + 101x_{101}^n = a_m m^n + a_{m-1} (m-1)^n + \cdots + a_1
where ai0,ia_i \ge 0, \forall i and a1++am=1+2++101a_1 + \dots + a_m = 1 + 2 + \dots + 101. Hence there exists sufficiently large nn such that
ammn++a11yyn=0(1) a_m m^n + \dots + a_1 - 1 - y \cdot y^n = 0 \quad (1)

The following lemma can help us find aia_i and yy.

Lemma: Given integers b1,,bNb_1, \cdots, b_N and suppose there exists sufficiently large nn such that b1+b22n+bNNN=0b_1+b_2 2^n+\cdots b_N N^N = 0. Then bi=0,ib_i = 0, \forall i.

Proof: Suppose some bib_i is not 0. Without loss of generality, let bN0b_N \neq 0. Dividing b1+b22n+bNNNb_1 + b_2 2^n + \cdots b_N N^N by NNN^N, we obtain
bN=bN1(N1N)n++b1(1N)n(bN1++b1)(N1N)n. |b_N| = |b_{N-1}|\left(\frac{N-1}{N}\right)^n + \cdots + b_1\left(\frac{1}{N}\right)^n \le (|b_{N-1}| + \cdots + |b_1|)\left(\frac{N-1}{N}\right)^n.
For sufficiently large nn, (N1N)n\left(\frac{N-1}{N}\right)^n is a sufficiently small number, which contradicts bN0b_N \neq 0.

Clearly, y>1y > 1. Applying the lemma to equation (1), we get am=y=m,a1=1a_m = y = m, a_1 = 1, and the other ai=0a_i = 0. From this we obtain (x1,,x101)=(1,m,,m)(x_1, \cdots, x_{101}) = (1, m, \cdots, m). But we have 1+m=a1++am=1++101=1+k1+m = a_1+\cdots+a_m = 1+\cdots+101 = 1+k so m=km=k.

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