AlgebraDifficulty 7.6National olympiad, round 2Find the answer
A sequence of real numbers a0,a1,… is said to be good if the following three conditions hold. (i) The value of a0 is a positive integer. (ii) For each non-negative integer i we have ai+1=2ai+1 or ai+1=ai+2ai. (iii) There exists a positive integer k such that ak=2014. Find the smallest positive integer n such that there exists a good sequence a0,a1,… of real numbers with the property that an=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+2ai+ai+2=ai+22(ai+1) Hence ai+1+11=21⋅ai+11 or ai+1+11=2(ai+1)ai+2=21⋅ai+11+21 Therefore, ak+11=2k1⋅a0+11+i=1∑k2k−i+1εi where εi=0 or 1. Multiplying both sides by 2k(ak+1) and putting ak=2014, we get 2k=a0+12015+2015⋅(i=1∑kεi⋅2i−1) where εi=0 or 1. Since gcd(2,2015)=1, we have a0+1=2015 and a0=2014. Therefore, 2k−1=2015⋅(i=1∑kεi⋅2i−1) where εi=0 or 1. We now need to find the smallest k such that 2015∣2k−1. Since 2015=5⋅13⋅31, from the Fermat little theorem we obtain 524−1,13212−1 and 31∣230−1. We also have lcm[4,12,30]=60, hence 5260−1,13260−1 and 31∣260−1, which gives 2015∣260−1. But 5∤230−1 and so k=60 is the smallest positive integer such that 2015∣2k−1. To conclude, the smallest positive integer k such that ak=2014 is when k=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.