Maths Olympiad Prep

Library / /8 of 45

Algebra Difficulty 8.2 Shortlist Prove it United States

Two sequences of integers, a1,a2,a3,a_1, a_2, a_3, \dots and b1,b2,b3,b_1, b_2, b_3, \dots, satisfy the equation
(anan1)(anan2)+(bnbn1)(bnbn2)=0 (a_n - a_{n-1})(a_n - a_{n-2}) + (b_n - b_{n-1})(b_n - b_{n-2}) = 0
for each integer nn greater than 22. Prove that there is a positive integer kk such that ak=ak+2008a_k = a_{k+2008}.

Solutions — 2

Solution 1

Define d(i,j)=(aiaj)2+(bibj)2d(i, j) = (a_i - a_j)^2 + (b_i - b_j)^2. Notice that
(anan1)2+(anan2)2(an1an2)2=2(anan1)(anan2) (a_n - a_{n-1})^2 + (a_n - a_{n-2})^2 - (a_{n-1} - a_{n-2})^2 = 2(a_n - a_{n-1})(a_n - a_{n-2})
and
(bnbn1)2+(bnbn2)2(bn1bn2)2=2(bnbn1)(bnbn2). (b_n - b_{n-1})^2 + (b_n - b_{n-2})^2 - (b_{n-1} - b_{n-2})^2 = 2(b_n - b_{n-1})(b_n - b_{n-2}).
Adding these two equations and using the given implies that
d(n,n1)+d(n,n2)d(n1,n2)=0, d(n, n-1) + d(n, n-2) - d(n-1, n-2) = 0,
hence
d(n,n1)=d(n1,n2)d(n,n2)d(n1,n2), d(n, n-1) = d(n-1, n-2) - d(n, n-2) \le d(n-1, n-2),
where equality holds if and only if an=an2a_n = a_{n-2} and bn=bn2b_n = b_{n-2}. Therefore, the sequence
{d(n,n1)}n=2=(d(2,1),d(3,2),d(4,3),) \{d(n, n-1)\}_{n=2}^{\infty} = (d(2, 1), d(3, 2), d(4, 3), \dots)
is nonincreasing. Since all the terms of this sequence are nonnegative integers, the sequence must eventually become constant: d(n,n1)=d(n1,n2)d(n, n-1) = d(n-1, n-2) for all sufficiently large nn, which in particular implies an=an2a_n = a_{n-2} for all sufficiently large nn. So whenever nn is large enough, we have
an+2008=an+2006=an+2004==an. a_{n+2008} = a_{n+2006} = a_{n+2004} = \dots = a_n.

Solution 2

(Based on work by Palmer Mebane) Let xn=anan1x_n = a_n - a_{n-1} and yn=bnbn1y_n = b_n - b_{n-1}. Then the given equation reads
xn(xn+xn1)+yn(yn+yn1)=0. x_n(x_n + x_{n-1}) + y_n(y_n + y_{n-1}) = 0.
To see this, note that 0(xn1+xn)2+(yn1+yn)20 \le (x_{n-1} + x_n)^2 + (y_{n-1} + y_n)^2, with equality if and only if xn=xn1x_n = -x_{n-1} and yn=yn1y_n = -y_{n-1}. Expanding and using the given equation we obtain
0=2xn(xn+xn1)+2yn(yn+yn1)(xn1+xn)2+(yn1+yn)2 0 = 2x_n(x_n + x_{n-1}) + 2y_n(y_n + y_{n-1}) \le (x_{n-1} + x_n)^2 + (y_{n-1} + y_n)^2
or
xn2+yn2xn12+yn12, x_n^2 + y_n^2 \le x_{n-1}^2 + y_{n-1}^2,
with equality if and only if xn=xn1x_n = -x_{n-1} and yn=yn1y_n = -y_{n-1}. Thus we have the claim.

Therefore, because xn2+yn20x_n^2 + y_n^2 \ge 0 is an integer, by the well-ordering principle, xn2+yn2<xn12+yn12x_n^2 + y_n^2 < x_{n-1}^2 + y_{n-1}^2 can only hold finitely many times. Thus there is a kk such that for all n>kn > k, xn=xn1x_n = -x_{n-1} and yn=yn1y_n = -y_{n-1}. This gives us the desired kk such that ak=ak+2008a_k = a_{k+2008}.

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.