Maths Olympiad Prep

Library / /37 of 48

Algebra Difficulty 7.7 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

A sequence of real numbers a0,a1,a_{0}, a_{1}, \ldots is said to be good\operatorname{good} if the following three conditions hold.
(i) The value of a0a_{0} is a positive integer.
(ii) For each non-negative integer ii we have ai+1=2ai+1a_{i+1}=2 a_{i}+1 or ai+1=aiai+2a_{i+1}=\frac{a_{i}}{a_{i}+2}.
(iii) There exists a positive integer kk such that ak=2014a_{k}=2014.
Find the smallest positive integer nn such that there exists a good sequence a0,a1,a_{0}, a_{1}, \ldots of real numbers with the property that an=2014a_{n}=2014.

Solution

Note that
ai+1+1=2(ai+1) or ai+1+1=ai+ai+2ai+2=2(ai+1)ai+2. a_{i+1}+1=2\left(a_{i}+1\right) \text{ or } a_{i+1}+1=\frac{a_{i}+a_{i}+2}{a_{i}+2}=\frac{2\left(a_{i}+1\right)}{a_{i}+2} .
Hence
1ai+1+1=121ai+1 or 1ai+1+1=ai+22(ai+1)=121ai+1+12. \frac{1}{a_{i+1}+1}=\frac{1}{2} \cdot \frac{1}{a_{i}+1} \text{ or } \frac{1}{a_{i+1}+1}=\frac{a_{i}+2}{2\left(a_{i}+1\right)}=\frac{1}{2} \cdot \frac{1}{a_{i}+1}+\frac{1}{2} .
Therefore,
1ak+1=12k1a0+1+i=1kεi2ki+1 \begin{equation*} \frac{1}{a_{k}+1}=\frac{1}{2^{k}} \cdot \frac{1}{a_{0}+1}+\sum_{i=1}^{k} \frac{\varepsilon_{i}}{2^{k-i+1}} \tag{1} \end{equation*}
where εi=0\varepsilon_{i}=0 or 11.
Multiplying both sides by 2k(ak+1)2^{k}\left(a_{k}+1\right) and putting ak=2014a_{k}=2014, we get
2k=2015a0+1+2015(i=1kεi2i1) 2^{k}=\frac{2015}{a_{0}+1}+2015 \cdot\left(\sum_{i=1}^{k} \varepsilon_{i} \cdot 2^{i-1}\right)
where εi=0\varepsilon_{i}=0 or 11.
Since gcd(2,2015)=1\operatorname{gcd}(2,2015)=1, we have a0+1=2015a_{0}+1=2015 and a0=2014a_{0}=2014. Therefore,
2k1=2015(i=1kεi2i1) 2^{k}-1=2015 \cdot\left(\sum_{i=1}^{k} \varepsilon_{i} \cdot 2^{i-1}\right)
where εi=0\varepsilon_{i}=0 or 11.
We now need to find the smallest kk such that 20152k12015 \mid 2^{k}-1. Since 2015=513312015= 5 \cdot 13 \cdot 31, from the Fermat little theorem we obtain 52415\mid 2^{4}-1, 13212113\mid 2^{12}-1 and 31230131 \mid 2^{30}-1. We also have lcm[4,12,30]=60\operatorname{lcm}[4,12,30]=60, hence 526015\mid 2^{60}-1, 13260113\mid 2^{60}-1 and 31260131 \mid 2^{60}-1, which gives 201526012015 \mid 2^{60}-1.
But 523015 \nmid 2^{30}-1 and so k=60k=60 is the smallest positive integer such that 20152k12015 \mid 2^{k}-1. To conclude, the smallest positive integer kk such that ak=2014a_{k}=2014 is when k=60k=60.

Alternative solution 1:
Clearly all members of the sequence are positive rational numbers. For each positive integer ii, we have ai=ai+112a_{i}=\frac{a_{i+1}-1}{2} or ai=2ai+11ai+1a_{i}=\frac{2 a_{i+1}}{1-a_{i+1}}. Since ai>0a_{i}>0 we deduce that
ai={ai+112 if ai+1>12ai+11ai+1 if ai+1<1 a_{i}= \begin{cases}\frac{a_{i+1}-1}{2} & \text{ if } a_{i+1}>1 \\ \frac{2 a_{i+1}}{1-a_{i+1}} & \text{ if } a_{i+1}<1\end{cases}
Thus aia_{i} is uniquely determined from ai+1a_{i+1}. Hence starting from ak=2014a_{k}=2014, we simply run the sequence backwards until we reach a positive integer. We compute as follows.
20141,20132,20114,20078,199916,198332,195164,1887128,1759256,1503512,9911024,198233,194966,1883132,1751264,1487528,9591056,191897,1821194,1627388,1239776,4631552,9261089,1852163,1689326,1363652,7111304,1422593,8291186,1658357,1301714,5871428,1174841,3331682,6661349,1332683,6491366,1298717,5811434,1162853,3091706,6181397,1236779,4571558,9141101,1828187,1641374,1267748,5191496,1038977,611954,1221893,2441771,4881527,9761039,195263,1889126,1763252,1511504,10071008,20141. \begin{aligned} & \frac{2014}{1}, \frac{2013}{2}, \frac{2011}{4}, \frac{2007}{8}, \frac{1999}{16}, \frac{1983}{32}, \frac{1951}{64}, \frac{1887}{128}, \frac{1759}{256}, \frac{1503}{512}, \frac{991}{1024}, \frac{1982}{33}, \frac{1949}{66}, \frac{1883}{132}, \frac{1751}{264}, \frac{1487}{528}, \frac{959}{1056}, \frac{1918}{97}, \frac{1821}{194}, \frac{1627}{388}, \\ & \frac{1239}{776}, \frac{463}{1552}, \frac{926}{1089}, \frac{1852}{163}, \frac{1689}{326}, \frac{1363}{652}, \frac{711}{1304}, \frac{1422}{593}, \frac{829}{1186}, \frac{1658}{357}, \frac{1301}{714}, \frac{587}{1428}, \frac{1174}{841}, \frac{333}{1682}, \frac{666}{1349}, \frac{1332}{683}, \frac{649}{1366}, \frac{1298}{717}, \frac{581}{1434}, \frac{1162}{853}, \\ & \frac{309}{1706}, \frac{618}{1397}, \frac{1236}{779}, \frac{457}{1558}, \frac{914}{1101}, \frac{1828}{187}, \frac{1641}{374}, \frac{1267}{748}, \frac{519}{1496}, \frac{1038}{977}, \frac{61}{1954}, \frac{122}{1893}, \frac{244}{1771}, \frac{488}{1527}, \frac{976}{1039}, \frac{1952}{63}, \frac{1889}{126}, \frac{1763}{252}, \frac{1511}{504}, \frac{1007}{1008}, \frac{2014}{1} . \end{aligned}
There are 61 terms in the above list. Thus k=60k=60.

Alternative solution 2:
Start with ak=m0n0a_{k}=\frac{m_{0}}{n_{0}} where m0=2014m_{0}=2014 and n0=1n_{0}=1 as in alternative solution 1. By inverting the sequence as in alternative solution 1, we have aki=minia_{k-i}=\frac{m_{i}}{n_{i}} for i0i \geq 0 where
(mi+1,ni+1)={(mini,2ni) if mi>ni(2mi,nimi) if mi<ni \left(m_{i+1}, n_{i+1}\right)= \begin{cases}\left(m_{i}-n_{i}, 2 n_{i}\right) & \text{ if } m_{i}>n_{i} \\ \left(2 m_{i}, n_{i}-m_{i}\right) & \text{ if } m_{i}<n_{i}\end{cases}
Easy inductions show that mi+ni=2015m_{i}+n_{i}=2015, 1mi,ni20141 \leq m_{i}, n_{i} \leq 2014 and gcd(mi,ni)=1\operatorname{gcd}\left(m_{i}, n_{i}\right)=1 for i0i \geq 0. Since a0N+a_{0} \in \mathbb{N}^{+} and gcd(mk,nk)=1\operatorname{gcd}\left(m_{k}, n_{k}\right)=1, we require nk=1n_{k}=1. An easy induction shows that (mi,ni)(2i,2i)(mod2015)\left(m_{i}, n_{i}\right) \equiv\left(-2^{i}, 2^{i}\right)(\bmod 2015) for i=0,1,,ki=0,1, \ldots, k.
Thus 2k1(mod2015)2^{k} \equiv 1(\bmod 2015). As in the official solution, the smallest such kk is k=60k=60. This yields nk1(mod2015)n_{k} \equiv 1(\bmod 2015). But since 1nk,mk20141 \leq n_{k}, m_{k} \leq 2014, it follows that a0a_{0} is an integer.

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 and solution reproduced as published; topic and difficulty added by this site.