Maths Olympiad Prep

Library / /35 of 106

Algebra Difficulty 8.2 Shortlist Find the answer

For each integer a0>1a_0 > 1, define the sequence a0,a1,a2,a_0, a_1, a_2, \ldots for n0n \geq 0 as
an+1={anif an is an integer,an+3otherwise.a_{n+1} = \begin{cases} \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\ a_n + 3 & \text{otherwise.} \end{cases}
Determine all values of a0a_0 such that there exists a number AA such that an=Aa_n = A for infinitely many values of nn.

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are given a sequence defined by a0,a1,a2, a_0, a_1, a_2, \ldots where the recurrence relation for n0 n \geq 0 is:
an+1={anif an is an integer,an+3otherwise. a_{n+1} = \begin{cases} \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer}, \\ a_n + 3 & \text{otherwise}. \end{cases}
The goal is to determine all starting values a0 a_0 such that the sequence an a_n reaches a specific number A A infinitely often.

### Analysis of the Sequence

1. Case for an Integer Square Root:

If an \sqrt{a_n} is an integer, denote it by k k , then an=k2 a_n = k^2 and an+1=k a_{n+1} = k . Repeated application will eventually bring the sequence to 1 unless it stops fluctuating between a finite set of values (possibly including 0).

2. Case without an Integer Square Root:

If an \sqrt{a_n} is not an integer, the sequence progresses by adding 3 repeatedly: an+1=an+3 a_{n+1} = a_n + 3 .

### Detecting a Recurrent A A

For the sequence to reach a number A A infinitely often, it must eventually stabilize in some way under these operations. This stability can occur if the process cycles or remains constant under the updates dictated by the sequence definition.

Consider a scenario where the progression via additions an+3 a_n + 3 may revert:
- The condition (3a0)(3 \mid a_0) implies:
a00(mod3) a_0 \equiv 0 \pmod{3}
Notice how, due to repeated additions by 3, any number that is initially divisible by 3 remains divisible by 3. Hence, the requirement (3a0)(3 \mid a_0) implies all members of the sequence remain in the residue class of 0 modulo 3.

### Conclusion:

If 3 divides a0 a_0 , then the repeated addition by 3 ensures that the sequence returns to specific numbers mod 3, thus maintaining periodicity and reaching certain values arbitrarily many times. However, if a0≢0(mod3) a_0 \not\equiv 0 \pmod{3} , then the condition for reaching a constant value A A over the sequence may fail. The sequence will not stabilize at an A A that's revisited infinitely often.

Thus, the values for a0 a_0 such that there exists a number A A where an=A a_n = A for infinitely many n n is:

3a0 \boxed{3 \mid a_0}

This completes our investigation, confirming the given reference answer by deriving its constraints through exploration of sequence behavior under modular arithmetic considerations.

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.