Maths Olympiad Prep

Library / /2 of 3

Number theory Difficulty 8.8 Shortlist Prove it Taiwan

Let nn be a positive integer. A strictly increasing arithmetic progression x0,x1,,xnx_0, x_1, \dots, x_n is called an nn-sequence if and only if
x0=a1×a2×a3××an,x1=b1×a2×a3××an,x2=b1×b2×a3××an,xn=b1×b2×b3××bn, \begin{align*} x_0 &= a_1 \times a_2 \times a_3 \times \dots \times a_n, \\ x_1 &= b_1 \times a_2 \times a_3 \times \dots \times a_n, \\ x_2 &= b_1 \times b_2 \times a_3 \times \dots \times a_n, \\ &\vdots \\ x_n &= b_1 \times b_2 \times b_3 \times \dots \times b_n, \end{align*}
for some positive integers a1,a2,,an,b1,b2,,bna_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n. Determine the smallest possible common difference among all nn-sequence (as a function of nn).

Solution

The smallest possible common difference is n!n!. Note that the common difference is
D=(b1a1)a2a3an=b1(b2a1)a3a4==b1b2bn1(bnan). D = (b_1 - a_1)a_2a_3 \cdots a_n = b_1(b_2 - a_1)a_3a_4 \cdots = \cdots = b_1b_2 \cdots b_{n-1}(b_n - a_n).
Moreover, since the sequence is strictly increasing, D>0D > 0, and hence bi>aib_i > a_i holds for all ii. Thus the above equation is equivalent to
(biai)ai+1=bi(bi+1ai+1) holding for all i. (b_i - a_i)a_{i+1} = b_i(b_{i+1} - a_{i+1}) \text{ holding for all } i.
Furthermore, since if ki=gcd(ai,bi)k_i = \text{gcd}(a_i, b_i), then replacing aia_i and bib_i by ai/kia_i/k_i and bi/kib_i/k_i still satisfies the conditions of the problem, we may assume without loss of generality that gcd(ai,bi)=1\text{gcd}(a_i, b_i) = 1 holds for all ii. In this case, the above equation forces us to have biai=bi+1ai+1b_i - a_i = b_{i+1} - a_{i+1} and ai+1=bia_{i+1} = b_i. Thus,
a1,a2=b1,a3=b2,,an=bn1,bn a_1, a_2 = b_1, a_3 = b_2, \cdots, a_n = b_{n-1}, b_n
must be a strictly increasing arithmetic progression. This means that, if the common difference of this sequence is d1d \ge 1, then
D=di=1n1(a1+id)1×i=1n1(1+i)=n!. D = d \prod_{i=1}^{n-1} (a_1 + id) \ge 1 \times \prod_{i=1}^{n-1} (1 + i) = n!.
Equality holds when ai=ia_i = i.

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.