Problem:
Given that a sequence satisfies x0​=0 and ∣xk​∣=∣xk−1​+3∣ for all integers k≥1, find the minimum possible value of ∣x1​+x2​+⋯+x2006​∣.
Solution:
The condition ∣xk​∣=∣xk−1​+3∣ is equivalent to xk2​=(xk−1​+3)2. Thus
k=1∑n+1​xk2​xn+12​k=0∑n​xk​​=k=1∑n+1​(xk−1​+3)2=k=0∑n​(xk​+3)2=(k=0∑n​xk2​)+(6k=0∑n​xk​)+9(n+1), so =k=1∑n+1​xk2​−k=0∑n​xk2​=(6k=0∑n​xk​)+9(n+1), and =61​[xn+12​−9(n+1)].​
Therefore ∣∣∣∣​∑k=12006​xk​∣∣∣∣​=61​∣∣∣​x20072​−18063∣∣∣​. Notice that xk​ is a multiple of 3 for all k, and that xk​ and k have the same parity. The requested sum will be a minimum when ∣∣∣​x20072​−18063∣∣∣​ is a minimum, that is, when x2007​ is the multiple of 3 whose square is as close as possible to 18063. Check odd multiples of 3, and find that 1292<16900,1412>19600, and 1352=18225. The requested minimum is therefore 61​∣∣∣​1352−18063∣∣∣​=27​, provided there exists a sequence that satisfies the given conditions and for which x2007​=135. An example of such a sequence is
xk​=⎩⎪⎪⎨⎪⎪⎧​3k−138135​ for k≤45 for k>45 and k even for k>45 and k odd ​​
The problems on this page are the property of the MAA's American Mathematics Competitions