Proving Constant Sequence of Positive Integers Starting with n

[Feldoh]

Let n be a positive integer. Define a sequence by setting a_1 = n and, for each k > 1, letting a_k be the unique integer in the range 0 \le a_k \le k-1[/itex] for which \displaystyle a_1 + a_2 + \cdots + a_k is divisible by k. For instance, when n = 9 the obtained sequence is \displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots. Prove that for any n the sequence \displaystyle a_1, a_2, a_3, \ldots eventually becomes constant.

 

[matticus]

that's cool, where'd you find this?

 

[abelian jeff]

Thanks, that was fun! I too would like to know where you found this problem!

Here is my attempt at a solution:

It is clear that once {\sum}^k_{i=1}{a_i}=ck for some c<k, subsequent terms in the sequence simply require additional c's to be added to them. Thus, we need to prove that for any starting n, there exists a k such that {\sum}^k_{i=1}{a_i}=ck for some c<k.

Assume not. That is, \forall{n} and \forall{k} (where n and k are positive integers), {\sum}^k_{i=1}{a_i}=Ck for some C\geq{k}.

Then we have

{k}^{2}\leq{Ck}=n+{a_2}+{a_3}+...+{a_k}\leq{n+1+2+...+(k-1)}={n+\frac{k(k+1)}{2}}=\frac{2n+k^{2}-k}{2}}

So by letting {n}\geq{\frac{k^{2}+k}{2}} for an arbitrary k, we derive a contradiction, for the sequence starting with n converges by the kth term. This completes the proof.



Is this correct?

 

[matt grime]

There is one flaw in the proof, mainly I think to do with how you've written it: n is fixed, you can't choose n; it doesn't make sense to say "let n be greater than (k^2+k)/2 for an arbitrary k".

It is also an unnecessary proof by contradiction. It suffices to note that given any n then for k sufficiently large n + k(k-1)/2 is less than k^2.

 

[abelian jeff]

Aaah, I see what you mean. Thanks for the correction!

 

[strings235]

haha, that's a usa math olympiad question. ah, reminds me of the good old days. looking forward to putnam in college

 

[ramsey2879]

Let n be a positive integer. Define a sequence by setting a_1 = n and, for each k &gt; 1, letting a_k be the unique integer in the range 0 \le a_k \le k-1[/itex] for which \displaystyle a_1 + a_2 + \cdots + a_k is divisible by k. For instance, when n = 9 the obtained sequence is \displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots. Prove that for any n the sequence \displaystyle a_1, a_2, a_3, \ldots eventually becomes constant.

<br /> define A(n) to be the least common multiple of the set {1,2,3...n} <br /> A(n) = {1,2,6,12,60,420,...}<br /> I noticed that if A_{m-1} &amp;lt; n \le A_{m} then {\sum}^k_{i=1}{a_i} \geq \frac{kA_{m}}{m} and a_{i} converges to \frac{A_{m}}{m} by the value of k equal to m. I thought I had a proof but need to come back to this later.

 

[Feldoh]

that's cool, where'd you find this?

It's actually from 2007 USA Mathematics Olympiad.

I found them here the solutions are there too. I had a lot of fun with the first one so I though I'd post it
http://www.artofproblemsolving.com/Wiki/index.php/2007_USAMO

 

[abelian jeff]

There is one flaw in the proof, mainly I think to do with how you've written it: n is fixed, you can't choose n; it doesn't make sense to say "let n be greater than (k^2+k)/2 for an arbitrary k".

It is also an unnecessary proof by contradiction. It suffices to note that given any n then for k sufficiently large n + k(k-1)/2 is less than k^2.

As I was falling asleep just now, this problem popped into my head, and I realized that I made an extremely stupid error, and if I had not made that error, I would have never made the mistake you pointed out (and I would have, presumably, had a wholly correct proof).

The error? I stated the negation incorrectly...I said "for all n" when I should have said "there exists an n". What a silly mistake. Oh well, its summer, I need to get these bloopers out of my system before the semester begins

 

[matt grime]

The error? I stated the negation incorrectly...I said "for all n" when I should have said "there exists an n".

No you shouldn't. n is given to you in the question. k is what you play with.

 

[abelian jeff]

Yes, it turns out that all you need to work with is the k. However, I said this:

Assume not. That is, \forall{n} and \forall{k} (where n and k are positive integers), {\sum}^k_{i=1}{a_i}=Ck for some C\geq{k}.

That is clearly incorrect.