Maths Olympiad Prep

Library / /27 of 48

Algebra Difficulty 7.6 National olympiad, round 2 Find the answer

A sequence of real numbers a0,a1,a_{0}, a_{1}, \ldots is said to be 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.

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

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 \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}} where εi=0\varepsilon_{i}=0 or 1. 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 1. 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 1. 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 5241,1321215\left|2^{4}-1,13\right| 2^{12}-1 and 31230131 \mid 2^{30}-1. We also have lcm[4,12,30]=60\operatorname{lcm}[4,12,30]=60, hence 52601,1326015\left|2^{60}-1,13\right| 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.

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.