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 [tex]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.[/tex]

 

[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 > 1$, letting $a_k$ be the unique integer in the range [tex]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.[/tex]

[tex] 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} < 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.[/tex]

 

[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.