Maths Olympiad Prep

Library / /336 of 383

Number theory Difficulty 9.0 IMO level Prove it IMO

Let a1,a2,,an,b1,b2,,bna_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n} be 2n2n positive integers such that the n+1n+1 products
a1a2a3an,b1a2a3an,b1b2a3an,b1b2b3bn \begin{gathered} a_{1} a_{2} a_{3} \cdots a_{n}, \\ b_{1} a_{2} a_{3} \cdots a_{n}, \\ b_{1} b_{2} a_{3} \cdots a_{n}, \\ \vdots \\ b_{1} b_{2} b_{3} \cdots b_{n} \end{gathered}
form a strictly increasing arithmetic progression in that order. Determine the smallest positive integer that could be the common difference of such an arithmetic progression.

Solution

Answer: The smallest common difference is n!n!.

Solution 1. The condition in the problem is equivalent to
D=(b1a1)a2a3an=b1(b2a2)a3a4an==b1b2bn1(bnan), D=\left(b_{1}-a_{1}\right) a_{2} a_{3} \cdots a_{n}=b_{1}\left(b_{2}-a_{2}\right) a_{3} a_{4} \cdots a_{n}=\cdots=b_{1} b_{2} \cdots b_{n-1}\left(b_{n}-a_{n}\right),
where DD is the common difference. Since the progression is strictly increasing, D>0D>0, hence bi>aib_{i}>a_{i} for every 1in1 \leqslant i \leqslant n. Individually, these equalities simplify to
(biai)ai+1=bi(bi+1ai+1) for every 1in1 \begin{equation*} \left(b_{i}-a_{i}\right) a_{i+1}=b_{i}\left(b_{i+1}-a_{i+1}\right) \text{ for every } 1 \leqslant i \leqslant n-1 \tag{1} \end{equation*}
If gi:=gcd(ai,bi)>1g_{i}:=\operatorname{gcd}\left(a_{i}, b_{i}\right)>1 for some 1in1 \leqslant i \leqslant n, then we can replace aia_{i} with aigi\frac{a_{i}}{g_{i}} and bib_{i} with bigi\frac{b_{i}}{g_{i}} to get a smaller common difference. Hence we may assume gcd(ai,bi)=1\operatorname{gcd}\left(a_{i}, b_{i}\right)=1 for every 1in1 \leqslant i \leqslant n.
Then, we have gcd(biai,bi)=gcd(ai,bi)=1\operatorname{gcd}\left(b_{i}-a_{i}, b_{i}\right)=\operatorname{gcd}\left(a_{i}, b_{i}\right)=1 and gcd(ai+1,bi+1ai+1)=gcd(ai+1,bi+1)=1\operatorname{gcd}\left(a_{i+1}, b_{i+1}-a_{i+1}\right)=\operatorname{gcd}\left(a_{i+1}, b_{i+1}\right)=1 for every 1in11 \leqslant i \leqslant n-1. The equality (1) implies ai+1=bia_{i+1}=b_{i} and biai=bi+1ai+1b_{i}-a_{i}=b_{i+1}-a_{i+1}. Thus,
a1,b1=a2,b2=a3,,bn1=an,bn a_{1}, \quad b_{1}=a_{2}, \quad b_{2}=a_{3}, \quad \ldots, \quad b_{n-1}=a_{n}, \quad b_{n}
is an arithmetic progression with positive common difference. Since a11a_{1} \geqslant 1, we have aiia_{i} \geqslant i for every 1in1 \leqslant i \leqslant n, so
D=(b1a1)a2a3an123n=n! D=\left(b_{1}-a_{1}\right) a_{2} a_{3} \cdots a_{n} \geqslant 1 \cdot 2 \cdot 3 \cdots n=n!
Equality is achieved when biai=1b_{i}-a_{i}=1 for 1in1 \leqslant i \leqslant n and a1=1a_{1}=1, i.e. ai=ia_{i}=i and bi=i+1b_{i}=i+1 for every 1in1 \leqslant i \leqslant n. Indeed, it is straightforward to check that these integers produce an arithmetic progression with common difference n!n!.

Solution 2 (Variant of Solution 1). Similarly to Solution 1, we may assume gcd(ai,bi)=1\operatorname{gcd}\left(a_{i}, b_{i}\right)=1 for every 1in1 \leqslant i \leqslant n.
Denote by p1,p2,,pn+1p_{1}, p_{2}, \ldots, p_{n+1} the sequence obtained as the product in the problem statement. Then we have pi+1pi=biai>1\frac{p_{i+1}}{p_{i}}=\frac{b_{i}}{a_{i}}>1, so bi>aib_{i}>a_{i}. Since p1,p2,,pn+1p_{1}, p_{2}, \ldots, p_{n+1} is an arithmetic progression, we have pi+2=2pi+1pip_{i+2}=2 p_{i+1}-p_{i} hence
2aibi=2biaibi=2pi+1pipi+1=pi+2pi+1=bi+1ai+1. 2-\frac{a_{i}}{b_{i}}=\frac{2 b_{i}-a_{i}}{b_{i}}=\frac{2 p_{i+1}-p_{i}}{p_{i+1}}=\frac{p_{i+2}}{p_{i+1}}=\frac{b_{i+1}}{a_{i+1}} .
But since the fractions on the left-hand side and the right-hand side are both irreducible, we conclude that bi=ai+1b_{i}=a_{i+1}, so 2aiai+1=ai+2ai+12-\frac{a_{i}}{a_{i+1}}=\frac{a_{i+2}}{a_{i+1}}. Then we have ai+ai+2=2ai+1a_{i}+a_{i+2}=2 a_{i+1}, which means that a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} is an arithmetic progression with positive common difference.
We conclude as in Solution 1.

Solution 3. (The following solution is purely algebraic: it does not involve considerations on greatest common divisors.)
We retake Solution 1 from (1). Then we have
ai+1bi+1ai+1=bibiai=1+aibiai. \frac{a_{i+1}}{b_{i+1}-a_{i+1}}=\frac{b_{i}}{b_{i}-a_{i}}=1+\frac{a_{i}}{b_{i}-a_{i}} .
So, for 1in1 \leqslant i \leqslant n,
aibiai=a1b1a1+(i1) \frac{a_{i}}{b_{i}-a_{i}}=\frac{a_{1}}{b_{1}-a_{1}}+(i-1)
Then
aiaibiai=a1b1a1+(i1)>i1 a_{i} \geqslant \frac{a_{i}}{b_{i}-a_{i}}=\frac{a_{1}}{b_{1}-a_{1}}+(i-1)>i-1
since biai1b_{i}-a_{i} \geqslant 1 and b1a1>0b_{1}-a_{1}>0. As aia_{i} is an integer, we have aiia_{i} \geqslant i.
We again conclude as in Solution 1.

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.