Maths Olympiad Prep

Library / /14 of 24

Algebra Difficulty 6.7 National Olympiad Prove it Italy

Problem:

Let hh be a positive integer and let ana_{n} be the sequence defined recursively as follows:
a0=1an+1={an2 if an is even an+h if an is odd. \begin{aligned} a_{0} & =1 \\ 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} \end{aligned}

(For example, if h=27h=27 we have: a1=28,a2=14,a3=7,a4=34,a5=17,a6=44,a_{1}=28, a_{2}=14, a_{3}=7, a_{4}=34, a_{5}=17, a_{6}=44, \ldots)

For which values of hh does there exist n>0n>0 such that an=1a_{n}=1?

Solution

Solution:

The values sought are all and only the odd positive integers. Indeed, if hh is even, then a1=1+ha_{1}=1+h is odd, hence a2=1+2ha_{2}=1+2 h is odd, and so on, so all the numbers an=1+nha_{n}=1+n h are odd and greater than 1.
If instead hh is odd, we observe that all the terms of the sequence are either positive integers less than or equal to hh or even positive integers greater than hh and less than or equal to 2h2 h. A simple proof of this fact can be obtained using the principle of induction. As the base case, we have a0=1a_{0}=1, which is a positive integer less than or equal to hh. Assuming the claim is true for ana_{n}, let us prove it for an+1a_{n+1}: if ana_{n} is odd and less than or equal to hh, then an+1=an+ha_{n+1}=a_{n}+h is even, greater than hh and less than or equal to 2h2 h; if instead ana_{n} is even and an2ha_{n} \leq 2 h, then an+1=an2ha_{n+1}=\frac{a_{n}}{2} \leq h.
It follows that the sequence of numbers ana_{n} can take only finitely many values. Since the sequence is infinite, there will exist two indices r<sr<s such that ar=asa_{r}=a_{s}. Suppose we choose two indices r<sr<s such that ar=asa_{r}=a_{s} and where rr is as small as possible. If r=0r=0, then as=a0=1a_{s}=a_{0}=1 and the claim is proved. Let us show by contradiction that we cannot have r>0r>0, distinguishing two cases:
- arha_{r} \leq h; then it cannot be that ar=ar1+ha_{r}=a_{r-1}+h or as=as1+ha_{s}=a_{s-1}+h, because in that case ar1a_{r-1} or as1a_{s-1} would not be positive, contradicting what was stated previously. Therefore ar1=as1=2ara_{r-1}=a_{s-1}=2 a_{r}, and thus we have an equality between two terms of the sequence in which the first term has an index smaller than rr, a contradiction;
- ara_{r} even, h<ar2hh<a_{r} \leq 2 h; then it cannot be that ar=ar12a_{r}=\frac{a_{r-1}}{2} or as=as12a_{s}=\frac{a_{s-1}}{2}, because otherwise ar1>2ha_{r-1}>2 h or as1>2ha_{s-1}>2 h, contradicting what was stated previously. Therefore ar1=as1=arha_{r-1}=a_{s-1}=a_{r}-h, and again we obtain the contradiction of an equality between two terms of the sequence in which the first term has an index smaller than rr.

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 translated into English from it; metadata (topic, difficulty) added by this project.