Maths Olympiad Prep

Library / /110 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Let hh be a positive integer. The sequence ana_n is defined by a0=1a_0 = 1 and

an+1={an2 if an is even an+h otherwise .a_{n+1} = \{\begin{array}{c} \frac{a_n}{2} \text{ if } a_n \text{ is even }\\\\a_n+h \text{ otherwise }.\end{array}

For example, h=27h = 27 yields a1=28,a2=14,a3=7,a4=34a_1=28, a_2 = 14, a_3 = 7, a_4 = 34 etc. For which hh is there an n>0n > 0 with an=1a_n = 1?

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

Solution

1. Initial Setup and Sequence Definition:
The sequence ana_n is defined by:
a0=1 a_0 = 1
and for n0n \geq 0,
an+1={an2if an is evenan+hif an is odd a_{n+1} = \begin{cases} \frac{a_n}{2} & \text{if } a_n \text{ is even} \\ a_n + h & \text{if } a_n \text{ is odd} \end{cases}

2. **Behavior Analysis for Even hh:**
If hh is even, we need to check if there exists an n>0n > 0 such that an=1a_n = 1.
- If ana_n is even, then an+1=an2a_{n+1} = \frac{a_n}{2}.
- If ana_n is odd, then an+1=an+ha_{n+1} = a_n + h.

Since hh is even, adding hh to an odd number results in an odd number. Thus, ana_n will never become 1 if it is odd and hh is even. Therefore, for even hh, there is no n>0n > 0 such that an=1a_n = 1.

3. **Behavior Analysis for Odd hh:**
If hh is odd, we need to check if there exists an n>0n > 0 such that an=1a_n = 1.
- If ana_n is even, then an+1=an2a_{n+1} = \frac{a_n}{2}.
- If ana_n is odd, then an+1=an+ha_{n+1} = a_n + h.

Since hh is odd, adding hh to an odd number results in an even number. This means that the sequence will alternate between even and odd numbers.

4. **Modulo hh Analysis:**
We analyze the sequence modulo hh. Notice that:
an+1{an2(modh)if an is evenan+han(modh)if an is odd a_{n+1} \equiv \begin{cases} \frac{a_n}{2} \pmod{h} & \text{if } a_n \text{ is even} \\ a_n + h \equiv a_n \pmod{h} & \text{if } a_n \text{ is odd} \end{cases}

Since a0=1a_0 = 1, we have a01(modh)a_0 \equiv 1 \pmod{h}. The sequence will eventually cycle through values modulo hh. By Euler's theorem, since ana_n is always less than 2h2h, there will be a time when ai1(modh)a_i \equiv 1 \pmod{h}.

5. Conclusion:
For odd hh, the sequence will eventually reach an=1a_n = 1 for some n>0n > 0. For even hh, the sequence will never reach an=1a_n = 1.

The final answer is h \boxed{ h } must be 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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.