Maths Olympiad Prep

Library / /53 of 53

Algebra Difficulty 7.8 National olympiad, round 2 Prove it Vietnam

An integer sequence (xn)(x_n) is defined as follows: 0x0<x11000 \le x_0 < x_1 \le 100 and
xn+2=7xn+1xn+280,n0. x_{n+2} = 7x_{n+1} - x_n + 280, \forall n \ge 0.

a. Prove that if x0=2,x1=3x_0 = 2, x_1 = 3 then for each positive integer nn, the sum of divisors of the following number is divisible by 24
xnxn+1+xn+1xn+2+xn+2xn+3+2018. x_n x_{n+1} + x_{n+1} x_{n+2} + x_{n+2} x_{n+3} + 2018.

b. Find all pairs (x0,x1)(x_0, x_1) such that xnxn+1+2019x_n x_{n+1} + 2019 are perfect squares for infinitely many numbers nn.

Solution

Lemma 1. If a positive integer nn satisfies 24n+124|n+1 then the sum of its positive divisors σ(n)\sigma(n) is divisible by 24.

Proof. Indeed, if dd is a divisor of nn then nd\frac{n}{d} is also a divisor of nn. Because n2(mod3)n \equiv 2 \pmod{3} so it cannot be a perfect square, which means the sum of its divisors can be divided into pairs of the form
d+nd=d2+nd. d + \frac{n}{d} = \frac{d^2 + n}{d}.
Note that n2(mod3)n \equiv 2 \pmod{3} and d21(mod3)d^2 \equiv 1 \pmod{3} so the sum above is divisible by 3.
On the other hand, n7(mod3)n \equiv 7 \pmod{3} and d1,3,5,7(mod8)d \equiv 1, 3, 5, 7 \pmod{8}, which implies d21(mod8)d^2 \equiv 1 \pmod{8} so the above sum is also divisible by 8. Since (3,8)=1(3, 8) = 1 then the above sum is divisible by 24 and the lemma is proved. \square

a.
Back to our problem, denote yn=xnxn+1+xn+1xn+2+xn+2xn+3y_n = x_n x_{n+1} + x_{n+1} x_{n+2} + x_{n+2} x_{n+3}, we need to prove that σ(yn+2018)\sigma(y_n + 2018) is divisible by 24. We also have 20182(mod24)2018 \equiv 2 \pmod{24} so according to the lemma, we need to show yn3(mod24)y_n \equiv -3 \pmod{24}.

Consider the period of the remainder when being divided by 3 of the sequence (xn)(x_n), note that xn+2xn+1xn+1(mod3)x_{n+2} \equiv x_{n+1} - x_n + 1 \pmod{3} we have 2, 0, 2, 0, 2, 0, ... this sequence is periodic with period 2 and
yn02+20+02=0(mod3). y_n \equiv 0 \cdot 2 + 2 \cdot 0 + 0 \cdot 2 = 0 \pmod{3}.

Similarly, consider the remainder of (xn)(x_n) when being divided by 8, note that xn+2xn+1xn(mod8)x_{n+2} \equiv -x_{n+1} - x_n \pmod{8} we have
2,3,3,2,3,3,2,3,3, 2, 3, 3, 2, 3, 3, 2, 3, 3, \dots
which means this sequence is periodic with period 3 and
yn23+33+32=5(mod8). y_n \equiv 2 \cdot 3 + 3 \cdot 3 + 3 \cdot 2 = 5 \pmod{8}.
It follows that (yn+3)(y_n + 3) is both divisible by 3, and 8, so yn3(mod24)y_n \equiv -3 \pmod{24} and a) is proved.

b.
Now, we prove the following lemma.

Lemma 2. Consider the integer sequence (zn)(z_n) satisfying zn+2=azn+1zn+bz_{n+2} = a z_{n+1} - z_n + b then the following quantity is constant
zn+12znzn+2bzn+1 for all n0. z_{n+1}^2 - z_n z_{n+2} - b z_{n+1} \text{ for all } n \ge 0.
Proof. Indeed, we have the following transformation
zn+12znzn+2bzn+1=zn+1(zn+1b)zn(azn+1zn+b)=zn+1(aznzn1)zn(azn+1zn+b)=zn2zn1zn+1bzn. \begin{aligned} z_{n+1}^2 - z_n z_{n+2} - b z_{n+1} &= z_{n+1}(z_{n+1} - b) - z_n(a z_{n+1} - z_n + b) \\ &= z_{n+1}(a z_n - z_{n-1}) - z_n(a z_{n+1} - z_n + b) \\ &= z_n^2 - z_{n-1} z_{n+1} - b z_n. \end{aligned}
The above equality holds for all n0n \ge 0 so zn+12znzn+2bzn+1=z12z0z2bz1=cz_{n+1}^2 - z_n z_{n+2} - b z_{n+1} = z_1^2 - z_0 z_2 - b z_1 = c where cc is a constant. \square

Thus, there exists CZC \in \mathbb{Z} such that xn+12xnxn+2280xn+1=Cx_{n+1}^2 - x_n x_{n+2} - 280 x_{n+1} = C. We have
xn+12xn(7xn+1xn+280)280xn+1=Cxn+12+xn27xn+1xn280(xn+1+xn)=C(xn+1+xn140)2=9(xn+1xn+2019)92019+C+1402un2=vn2+C+1429, \begin{aligned} x_{n+1}^2 - x_n(7 x_{n+1} - x_n + 280) - 280 x_{n+1} &= C \\ x_{n+1}^2 + x_n^2 - 7 x_{n+1} x_n - 280(x_{n+1} + x_n) &= C \\ (x_{n+1} + x_n - 140)^2 &= 9(x_{n+1} x_n + 2019) - 9 \cdot 2019 + C + 140^2 \\ u_n^2 &= v_n^2 + C + 1429, \end{aligned}
where un=xn+1+xn140u_n = x_{n+1} + x_n - 140, vn=3xn+1xn+2019v_n = 3\sqrt{x_{n+1} x_n + 2019} for all n0n \ge 0.

Since (xn)(x_n) is an increasing integer sequence so it is unbounded, thus (un)(u_n) is increasing and unbounded. It is also clear that if xnxn+1+2019x_n x_{n+1} + 2019 is a perfect square then vnZ+v_n \in \mathbb{Z}^+.

Hence, un+vnC+1429u_n + v_n | C + 1429 for infinite values of nn. Clearly, this case only happens when C+1429=0C + 1429 = 0 so
(xn+1+xn140)2=9(xn+1xn+2019),nZ+. (x_{n+1} + x_n - 140)^2 = 9(x_{n+1} x_n + 2019), \forall n \in \mathbb{Z}^+.
We have (x0+x1140)220199>44232=1322(x_0 + x_1 - 140)^2 \ge 2019 \cdot 9 > 44^2 \cdot 3^2 = 132^2 so 140x0x1133|140 - x_0 - x_1| \ge 133, but 0x0<x1<1010 \le x_0 < x_1 < 101 then 140(x0+x1)133140 - (x_0 + x_1) \ge 133, i.e. x0+x17x_0 + x_1 \le 7. We also have
C=x12+x027x1x0280(x1+x0)=1429. C = x_1^2 + x_0^2 - 7 x_1 x_0 - 280(x_1 + x_0) = -1429.
Notice that x12+x0249x_1^2 + x_0^2 \le 49 so 1429=C<49280(x1+x0)-1429 = C < 49 - 280(x_1 + x_0), which implies x0+x15x_0 + x_1 \ge 5. By direct checking, the case x1+x0=7x_1 + x_0 = 7 and x1+x0=6x_1 + x_0 = 6 has no solution. So x0+x1=5x_0 + x_1 = 5, which implies x0x1=6x_0 x_1 = 6 so it's easy to see that x0=2,x1=3x_0 = 2, x_1 = 3.

Therefore, (x0,x1)=(2,3)(x_0, x_1) = (2, 3) is the only satisfying pair. \square

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 and solution reproduced as published; topic and difficulty added by this site.