Maths Olympiad Prep

Library / /486 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Prove it

Find all positive integers n2n \geqslant 2 for which there exist nn real numbers a1<a2<<ana_{1}<a_{2}<\cdots<a_{n} and a positive real number rr such that the 12n(n1)\frac{1}{2} n(n-1) differences ajaia_{j}-a_{i} for 1i<jn1 \leqslant i<j \leqslant n are equal, in some order, to the numbers r1,r2,,r12n(n1)r^{1}, r^{2}, \ldots, r^{\frac{1}{2} n(n-1)}. (Czech Republic)

Solution

We first show a solution for each n{2,3,4} n \in \{2,3,4\} . We will later show the impossibility of finding such a solution for n5 n \geqslant 5 . For n=2 n=2 , take for example (a1,a2)=(1,3) (a_{1}, a_{2}) = (1,3) and r=2 r=2 . For n=3 n=3 , take the root r>1 r > 1 of x2x1=0 x^{2} - x - 1 = 0 (the golden ratio) and set (a1,a2,a3)=(0,r,r+r2) (a_{1}, a_{2}, a_{3}) = (0, r, r + r^{2}) . Then
(a2a1,a3a2,a3a1)=(r,r2,r+r2=r3) (a_{2} - a_{1}, a_{3} - a_{2}, a_{3} - a_{1}) = (r, r^{2}, r + r^{2} = r^{3})
For n=4 n=4 , take the root r(1,2) r \in (1,2) of x3x1=0 x^{3} - x - 1 = 0 (such a root exists because 1311<0 1^{3} - 1 - 1 < 0 and 2321>0 2^{3} - 2 - 1 > 0 ) and set (a1,a2,a3,a4)=(0,r,r+r2,r+r2+r3) (a_{1}, a_{2}, a_{3}, a_{4}) = (0, r, r + r^{2}, r + r^{2} + r^{3}) . Then
(a2a1,a3a2,a4a3,a3a1,a4a2,a4a1)=(r,r2,r3,r4,r5,r6) (a_{2} - a_{1}, a_{3} - a_{2}, a_{4} - a_{3}, a_{3} - a_{1}, a_{4} - a_{2}, a_{4} - a_{1}) = (r, r^{2}, r^{3}, r^{4}, r^{5}, r^{6})
For n5 n \geqslant 5 , we will proceed by contradiction. Suppose there exist numbers a1<a2<<an a_{1} < a_{2} < \cdots < a_{n} and r>1 r > 1 satisfying the conditions of the problem. We start with a lemma:

Lemma. We have rn1>2 r^{n-1} > 2 .

Proof. There are only n1 n-1 differences ajai a_{j} - a_{i} with j=i+1 j = i+1 , so there exists an exponent en e \leqslant n and a difference ajai a_{j} - a_{i} with ji+2 j \geqslant i+2 such that ajai=re a_{j} - a_{i} = r^{e} . This implies
rnre=ajai=(ajaj1)+(aj1ai)>r+r=2r, r^{n} \geqslant r^{e} = a_{j} - a_{i} = (a_{j} - a_{j-1}) + (a_{j-1} - a_{i}) > r + r = 2r,
thus rn1>2 r^{n-1} > 2 as desired.

To illustrate the general approach, we first briefly sketch the idea behind the argument in the special case n=5 n=5 . In this case, we clearly have a5a1=r10 a_{5} - a_{1} = r^{10} . Note that there are 3 ways to rewrite a5a1 a_{5} - a_{1} as a sum of two differences, namely
(a5a4)+(a4a1),(a5a3)+(a3a1),(a5a2)+(a2a1). (a_{5} - a_{4}) + (a_{4} - a_{1}), (a_{5} - a_{3}) + (a_{3} - a_{1}), (a_{5} - a_{2}) + (a_{2} - a_{1}).
Using the lemma above and convexity of the function f(n)=rn f(n) = r^{n} , we argue that those three ways must be r10=r9+r1=r8+r4=r7+r6 r^{10} = r^{9} + r^{1} = r^{8} + r^{4} = r^{7} + r^{6} . That is, the "large" exponents keep dropping by 1, while the "small" exponents keep increasing by n2,n3,,2 n-2, n-3, \ldots, 2 . Comparing any two such equations, we then get a contradiction unless n4 n \leqslant 4 .

Now we go back to the full proof for any n5 n \geqslant 5 . Denote b=12n(n1) b = \frac{1}{2} n(n-1) . Clearly, we have ana1=rb a_{n} - a_{1} = r^{b} . Consider the n2 n-2 equations of the form:
ana1=(anai)+(aia1) for i{2,,n1} a_{n} - a_{1} = (a_{n} - a_{i}) + (a_{i} - a_{1}) \text{ for } i \in \{2, \ldots, n-1\}
In each equation, one of the two terms on the right-hand side must be at least 12(ana1) \frac{1}{2} (a_{n} - a_{1}) . But from the lemma we have rb(n1)=rb/rn1<12rb r^{b-(n-1)} = r^{b} / r^{n-1} < \frac{1}{2} r^{b} , so the other term must be at least 12(ana1) \frac{1}{2} (a_{n} - a_{1}) . Therefore, we can write
ana1=rb=rαi+rβi a_{n} - a_{1} = r^{b} = r^{\alpha_{i}} + r^{\beta_{i}}
for some αi \alpha_{i} and βi \beta_{i} with αib(n1) \alpha_{i} \geqslant b - (n-1) and βib(n1) \beta_{i} \leqslant b - (n-1) . Since r>1 r > 1 and f(r)=rn f(r) = r^{n} is convex, we have
rb1rb2>rb2rb3>>rb(n3)rb(n2) r^{b-1} - r^{b-2} > r^{b-2} - r^{b-3} > \ldots > r^{b-(n-3)} - r^{b-(n-2)}
implying
rα2rα1>rα3rα2>>rαn2rαn3. r^{\alpha_{2}} - r^{\alpha_{1}} > r^{\alpha_{3}} - r^{\alpha_{2}} > \ldots > r^{\alpha_{n-2}} - r^{\alpha_{n-3}}.
Convexity of f(r)=rn f(r) = r^{n} further implies
α2α1>α3α2>>αn2αn3. \alpha_{2} - \alpha_{1} > \alpha_{3} - \alpha_{2} > \ldots > \alpha_{n-2} - \alpha_{n-3}.
Note that αn2αn32 \alpha_{n-2} - \alpha_{n-3} \geqslant 2 : Otherwise we would have αn2αn3=1 \alpha_{n-2} - \alpha_{n-3} = 1 and thus
rαn3(r1)=rαn2rαn3=rb(n3)rb(n2)=rb(n2)(r1), r^{\alpha_{n-3}} \cdot (r-1) = r^{\alpha_{n-2}} - r^{\alpha_{n-3}} = r^{b-(n-3)} - r^{b-(n-2)} = r^{b-(n-2)} \cdot (r-1),
implying that αn3=b(n2) \alpha_{n-3} = b - (n-2) , a contradiction. Therefore, we have
αn2α1=(αn2αn3)++(α2α1)2+3++(n2)=12(n2)(n1)1=12n(n3) \begin{aligned} \alpha_{n-2} - \alpha_{1} & = (\alpha_{n-2} - \alpha_{n-3}) + \cdots + (\alpha_{2} - \alpha_{1}) \\ & \geqslant 2 + 3 + \cdots + (n-2) \\ & = \frac{1}{2} (n-2)(n-1) - 1 = \frac{1}{2} n(n-3) \end{aligned}
On the other hand, from αn2b(n1) \alpha_{n-2} \leqslant b - (n-1) and α11 \alpha_{1} \geqslant 1 we get
αn2α1bn=12n(n1)n=12n(n3), \alpha_{n-2} - \alpha_{1} \leqslant b - n = \frac{1}{2} n(n-1) - n = \frac{1}{2} n(n-3),
implying that equalities must occur everywhere and the claim about the small terms follows. Now, assuming n22 n-2 \geqslant 2 , we have the two different equations:
rb=rb(n2)+rb(n2)1 and rb=rb(n3)+rb(n2)3, r^{b} = r^{b-(n-2)} + r^{b-(n-2)-1} \text{ and } r^{b} = r^{b-(n-3)} + r^{b-(n-2)-3},
which can be rewritten as
rn1=r+1 and rn+1=r4+1 r^{n-1} = r + 1 \quad \text{ and } \quad r^{n+1} = r^{4} + 1
Simple algebra now gives
r4+1=rn+1=rn1r2=r3+r2(r1)(r3r1)=0. r^{4} + 1 = r^{n+1} = r^{n-1} \cdot r^{2} = r^{3} + r^{2} \Longrightarrow (r-1)(r^{3} - r - 1) = 0.
Since r1 r \neq 1 , using Equation (1) we conclude r3=r+1=rn1 r^{3} = r + 1 = r^{n-1} , thus n=4 n = 4 , which gives a contradiction.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.