Maths Olympiad Prep

Library / /177 of 196

Algebra Difficulty 6.2 National Olympiad Prove it Soviet Union

Problem:
What is the maximum possible length of a sequence of natural numbers x1,x2,x3,…x_{1}, x_{2}, x_{3}, \ldots such that xi≤1998x_{i} \leq 1998 for i≥1i \geq 1, and xi=∣xi−1−xi−2∣x_{i} = |x_{i - 1} - x_{i - 2}| for i≥3i \geq 3.

Solution

Solution:
Answer 2998.
The sequence is completely determined by its first two elements. If the largest element of the sequence is nn, then it must occur as one of the first two elements. Because x3x_{3} and x4x_{4} are both smaller than the largest of the first two elements and hence all subsequent elements are too.

Let f(n,m)f(n, m) be the length of the sequence with x1=nx_{1} = n, x2=mx_{2} = m. It is straightforward to verify by induction that f(1,2n)=f(2n−1,2n)=3n+1f(1,2n) = f(2n - 1,2n) = 3n + 1, f(2n,1)=f(2n,2n−1)=3nf(2n,1) = f(2n,2n - 1) = 3n, f(2n,2n+1)=3n+3f(2n,2n + 1) = 3n + 3, f(1,2n+1)=f(2n+1,1)=3n+2f(1,2n + 1) = f(2n + 1,1) = 3n + 2, f(2n+1,2n)=3n+1f(2n + 1,2n) = 3n + 1. A rather more fiddly induction then shows that these are the best possible lengths. Hence the longest sequence with no element more than 1998 is that starting 1,19981, 1998 which has length 2998.

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.