Maths Olympiad Prep

Library / /21 of 27

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

Let uu be a positive rational number and mm be a positive integer. Define a sequence q1,q2,q3,q_1,q_2,q_3,\dotsc such that q1=uq_1=u and for n2n\geqslant 2:
if qn1=ab for some relatively prime positive integers a and b, then qn=a+mbb+1.\text{if }q_{n-1}=\frac{a}{b}\text{ for some relatively prime positive integers }a\text{ and }b, \text{ then }q_n=\frac{a+mb}{b+1}.
Determine all positive integers mm such that the sequence q1,q2,q3,q_1,q_2,q_3,\dotsc is eventually periodic for any positive rational number uu.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider the sequence q1,q2,q3, q_1, q_2, q_3, \ldots defined by the initial term q1=u q_1 = u , where u u is a positive rational number, and the recursive relation for n2 n \geq 2 :

qn=a+mbb+1ifqn1=ab, q_n = \frac{a + mb}{b + 1} \quad \text{if} \quad q_{n-1} = \frac{a}{b},

where a a and b b are positive integers that are relatively prime.

We seek all positive integers m m such that the sequence becomes eventually periodic for any positive rational number u u .

### Analysis of the Sequence

1. Rational Structure:
Each qn q_n is a rational number of the form anbn \frac{a_n}{b_n} , where an a_n and bn b_n are integers. The expression for qn q_n ensures an=an1+mbn1 a_n = a_{n-1} + mb_{n-1} and bn=bn1+1 b_n = b_{n-1} + 1 .

2. Behavior of the Sequence:
Since bn=b1+(n1) b_n = b_1 + (n-1) , it increases linearly, starting from b1 b_1 , as n n increases. As the sequence continues, bn b_n \to \infty .

3. Criteria for Periodicity:
The sequence q1,q2,q3, q_1, q_2, q_3, \ldots becomes eventually periodic if there exists integers p p and L L such that qp+L=qp q_{p+L} = q_p .

4. Condition on m:

- The recursive relation can be reflected in a difference equation involving consecutive terms,

anan1=m(bn1bn+1)=m1. a_n - a_{n-1} = m(b_{n-1} - b_n + 1) = m - 1.

Thus, the sequence anmodbn a_n \mod b_n will determine periodic behavior, and a key observation is:

- For the sequence to repeat, especially when qn=anbn q_n = \frac{a_n}{b_n} , the condition that numbers anan+Lmodbn a_n \equiv a_{n+L} \mod b_n must be satisfied together with the structure of m m .

5. Observations on Parity:

- If m m is odd, the increments anan+1mod2 a_n \equiv a_{n+1} \mod 2. This indicates a simplified condition for periodicity as the eligibilities for even differences entail periodic occurrence in modular arithmetic.

- If m m is even, there may be no periodicity due to disparities in balance induced by alternating arrangements.

Hence, for the sequence to become eventually periodic regardless of the initial rational number u u , m m must be an odd integer.

Therefore, the final solution is:

m is odd \boxed{m \text{ is odd}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.