Maths Olympiad Prep

Library / /21 of 29

Algebra Difficulty 5.9 AIME, harder Prove it Croatia

a0=1,an+1={an2,if an is even,an+d,if an is odd. a_0 = 1, \quad a_{n+1} = \begin{cases} \frac{a_n}{2}, & \text{if } a_n \text{ is even,} \\ a_n + d, & \text{if } a_n \text{ is odd.} \end{cases}
Determine all dd such that an=1a_n = 1 for some n>0n > 0. (Italy 2005)

Solution

First notice that for even dd the sequence is of the form an=1+nda_n = 1 + nd, i.e. all the terms of the sequence are odd and the sequence is monotonically increasing. Therefore an1a_n \neq 1 for n>0n > 0.

Let dd be an arbitrary odd number. We can easily show by induction that an<da_n < d if ana_n is odd, and an<2da_n < 2d if ana_n is even. Thus the sequence is limited, so it is periodic.

Let rr be the smallest index such that ar=asa_r = a_s for some srs \neq r. Assume r>0r > 0.
If arda_r \le d, that means that ara_r (and then also asa_s) is derived from the previous term by dividing by 2, i.e. ar=ar1/2a_r = a_{r-1}/2, as=as1/2a_s = a_{s-1}/2, so it follows that ar1=as1a_{r-1} = a_{s-1}, and this is in contradiction with minimality of rr.
If ar>da_r > d, from an2da_n \le 2d we conclude that ara_r and asa_s are derived from previous terms of the sequence by adding dd, so again it follows that ar1=as1a_{r-1} = a_{s-1}, and again we have a contradiction with the minimality of rr.

Hence, r=0r = 0 and as=a0=1a_s = a_0 = 1 for some s>0s > 0 for every odd dd.

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.