Define the sequences an,bn,cn as follows. a0=k,b0=4,c0=1. If an is even then an+1=an2, bn+1=2bn, cn+1=cn. If an is odd, then an+1=an−bn2−cn, bn+1=bn, cn+1=bn+cn. Find the number of positive integers k<1995 such that some an=0.
Problem
Source: IMO Shortlist 1994, N4
Tags: number theory, IMO Shortlist, Sequence, recurrence relation
25.04.2011 05:50
Any solutions to this fine, fine problem?
18.05.2014 07:34
Does anybody have the official solutions or an own solution???
07.06.2014 19:18
Can anyone prove that an integer is good(i.e satisfies the given conditions) if and only if it is of the form k(2k+1) where k is a natural number?
08.06.2014 09:14
**** Incorrect solution due to incorrect reading of problem statement (see my post after the next) *** Note that the recursive definition of bn depends only on bn itself, and the recursive definition of cn depends only on bn and cn. One easily gets per induction that b2n−1=b2n=22+n and c2n=c2n+1=23+n−7. With this it follows again per indicution (because all bn,cn≥0) that, if an0<0 then an<0 for all n≥n0. However, to solve this problem, one needs only to calculate the bn,cn values for n≤10 recursively and use them for the an recurrence (sorry, I have no idea how to make a table, any help would be appreciated): n bn cn 0 4 1 1 8 1 2 8 9 3 16 9 4 16 25 5 32 25 6 32 57 7 64 57 8 64 121 9 128 121 10 128 249 n an 0 k 1 12k 2 12k−5 3 14k−52 4 14k−392 5 18k−394 6 18k−2034 7 116k−2038 8 116k−9158 9 132k−91516 10 132k−387516 We see: For k<1995, a10<0 and hence by the above observation an<0 for all n≥10. So an=0 is only possible for n<10 and solving an=0 for 0≤n≤9 gives as possible solutions k=10,78,406,1830 (k=0 not possible as k is positive according to problem statement). So there are 4 such positive integers k as sought in the problem statement. @hajimbrak: All the solutions are of the stated form: 10=2∗5, 78=6∗13, 406=14∗29 and 1830=30∗61. Note that the smaller factor is each time one bigger than the larger factor if the previous solution. But of course, not all the intergers of the form m∗(2m+1) are solutions. I guess it is straightforward to find all the solutions. You have to guess and then prove by induction the general formula for an, starting at the above given formulas for bn and cn.
08.06.2014 09:20
Here is a proof of the fact that all integers of the form k(2k+1) are good. Let 2a be the largest power of 2 less than k.Hence k=2a+b where 0≤b<2a.Now we prove by induction that for some n, an=2a+1+4b+1,bn=2a+2,cn=4b+1 which also implies that an+1=0. We can easily check the statement for the few base cases.Now we assume that the statement is true for all k less than 2l. Let k=2l+m,where 2l is the largest power of two less than k.Hence a0=k(2k+1)=22l+1+(4m+1)2l+m(2m+1) Now m is less than 2l hence the statement is true for it.Hence after sometime the term m(2m+1) will vanish and for some n we will get an=2r+l+1+(4m+1)2r,bn=2l−r+2,cn=4m+1 which implies that an+r+1=0.
08.06.2014 09:26
@Ingix:I do not think your solution is correct because I have given a proof of the fact that all numbers of the form k(2k+1) are good,hence their are more than four solutions.You can check that 21,36,3,55etc all are solutions.In fact the correct answer is 31,you can get a solution in the IMO Compendium.
08.06.2014 09:47
Sorry, I screwed up. I read "If an is even/odd" as "if n is even/odd", thus leading to my incorrect solution above.
16.06.2014 10:21
For the other part, we refer to the proof given in the IMO compendium where it is proved that if an=0 then bn−1,cn−1 uniquely fixes a0.Now let bn−1=2m and cn−1=4k+1.We choose l=2m−2+k and a0=l(2l+1).This satisfies the conditions according to the proof of the other part and it is unique.Hence it is proved that an integer is good if and only if it is of the form a(2a+1).
23.10.2017 06:28
1. It's easy to verify that an.bn+c2n2 is an invariant. Also, cn≡1(mod4) ∀n∈N. Therefore, if an=0 for some n, then let cn=4u+1⇒4a0+12=(4u+1)22⇒a0=u(2u+1). 2. Now we prove that all a0 of the form u(2u+1) will give an=0 for some n. Let u=2x1+2x2+...+2xk(x1<x2<...<xk) For k=1, i.e. u=2x1, it's easy to show that ax1+1=0. Consider k≥2. Denote vi=∑kj=i+12xj−xi+1 ∀1≤i≤k−1 and vk=1 By induction, axi+i=2xi+1−xi.vi+1.(2xi+1+1.vi+1+∑ij=12xj+2+1), bxi+i=2xi+2, cxi+i=∑ij=12xj+2+1 ∀1≤i≤k−1 ⇒axk−1+k−1=2xk−xk−1.vk.(2xk+1.vk+∑k−1j=12xj+2+1)=2xk−xk−1.(2xk+1+∑k−1j=12xj+2+1), bxk−1+k−1=2xk−1+2, cxk−1+k−1=∑k−1j=12xj+2+1 ⇒axk+k−1=2xk+1+∑k−1j=12xj+2+1, bxk+k−1=2xk+2, cxk+k−1=∑k−1j=12xj+2+1 ⇒axk+k=0. ◼