Maths Olympiad Prep

Library / /27 of 31

Algebra Difficulty 7.4 National Olympiad, round 2 Prove it Italy

Problem:

Let x1,x2,x3,x_{1}, x_{2}, x_{3}, \ldots be the sequence defined recursively as follows:
{x1=4xn+1=x1x2x3xn+5 for n1 \left\{\begin{array}{l} x_{1}=4 \\ x_{n+1}=x_{1} x_{2} x_{3} \cdots x_{n}+5 \quad \text{ for } n \geq 1 \end{array}\right.
(The first terms of the sequence are thus x1=4,x2=4+5=9,x3=49+5=41,x_{1}=4, x_{2}=4+5=9, x_{3}=4 \cdot 9+5=41, \ldots ) Find all pairs of positive integers {a,b}\{a, b\} such that xaxbx_{a} x_{b} is a perfect square.

Solution

Solution:

We will show that the only pair satisfying the conditions of the problem is {1,2}\{1,2\}. (Clearly there is also a solution if a=b=na=b=n for every nn, but in this case {a,b}\{a, b\} is not a pair; whether or not this case has been considered has no bearing on the grading anyway).
We may of course assume, by symmetry, that a>ba>b.

For n2n \geq 2, using the fact that x1xn1=xn5x_{1} \ldots x_{n-1}=x_{n}-5, we can also write xn+1=(x1xn1)xn+5=(xn5)xn+5=xn25xn+5x_{n+1}=\left(x_{1} \ldots x_{n-1}\right) x_{n}+5=\left(x_{n}-5\right) x_{n}+5=x_{n}^{2}-5 x_{n}+5.
Observe that for a>ba>b we have xa=x1xbxa1+5x_{a}=x_{1} \ldots x_{b} \ldots x_{a-1}+5, so, if a prime divides both xax_{a} and xbx_{b}, then it divides xax1xbxa1=5x_{a}-x_{1} \ldots x_{b} \ldots x_{a-1}=5.
However, 5 divides xn+1=xn25xn+5x_{n+1}=x_{n}^{2}-5 x_{n}+5 if and only if it divides xnx_{n}: it follows that if a term of the sequence is not divisible by 5, neither is the following one. Since x1x_{1} is not divisible by 5, no term of the sequence is divisible by 5.
This shows that xax_{a} and xbx_{b} never have common prime divisors, so xaxbx_{a} x_{b} is a perfect square if and only if both xax_{a} and xbx_{b} are: we therefore look for which perfect squares occur in the sequence.
Certainly x1=4x_{1}=4 and x2=9x_{2}=9 are squares, so {1,2}\{1,2\} is a solution.
On the other hand, since x2=9x_{2}=9, for n2n \geq 2 the number xnx_{n} is of the form xn=9k+5x_{n}=9 k+5 and hence, in particular, leaves remainder 2 upon division by 3. Now it is easy to check that no square has this property, since the square of a multiple of 3 is a multiple of 3 while the square of a number of the form 3m±13 m \pm 1 is 9m2±6m+19 m^{2} \pm 6 m+1 and hence leaves remainder 1 upon division by 3. Hence there are no other solutions besides the one found.

Alternatively, in a perhaps more elementary form, since for n2n \geq 2 we have xn+1=xn25xn+5x_{n+1}=x_{n}^{2}-5 x_{n}+5, we can study the equation x25x+5=a2x^{2}-5 x+5=a^{2} with x,ax, a positive integers.
Multiplying both sides by 4 we obtain
4a2=4x220x+20=(2x5)255=(2x5)24a2(2x2a5)(2x+2a5)=5. \begin{gathered} 4 a^{2}=4 x^{2}-20 x+20=(2 x-5)^{2}-5 \Rightarrow 5=(2 x-5)^{2}-4 a^{2} \\ \Rightarrow(2 x-2 a-5)(2 x+2 a-5)=5 . \end{gathered}
Since 5 is only divisible by ±1,±5\pm 1, \pm 5 and 2x+a5>2xa52 x+a-5>2 x-a-5, there are only the two possibilities 2x+2a5=1,2x2a5=52 x+2 a-5=-1, 2 x-2 a-5=-5 and 2x+2a5=5,2x2a5=12 x+2 a-5=5, 2 x-2 a-5=1, which lead respectively to x=1,a=1x=1, a=1 and x=4,a=1x=4, a=1. The number 1, however, cannot appear in the sequence, because x1=4x_{1}=4 and each term is larger than the previous one.
We deduce again that no perfect squares appear in the sequence, apart from x1=4,x2=9x_{1}=4, x_{2}=9 (which are not expressed in the form x25x+5x^{2}-5 x+5).

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