MathDB

1

Part of 2007 USAMO

Problems(1)

sequence (.) eventually becomes constant.

Source: USAMO 2007

4/26/2007
Let nn be a positive integer. Define a sequence by setting a1=na_{1}= n and, for each k>1k > 1, letting aka_{k} be the unique integer in the range 0≤ak≤k−10\leq a_{k}\leq k-1 for which a1+a2+...+aka_{1}+a_{2}+...+a_{k} is divisible by kk. For instance, when n=9n = 9 the obtained sequence is 9,1,2,0,3,3,3,...9,1,2,0,3,3,3,.... Prove that for any nn the sequence a1,a2,...a_{1},a_{2},... eventually becomes constant.
inductionnumber theory proposednumber theoryInequality