Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difficult Proof

  1. Aug 15, 2007 #1
    Let [itex]n[/itex] be a positive integer. Define a sequence by setting [itex]a_1 = n[/itex] and, for each [itex]k > 1[/itex], letting [itex]a_k[/itex] be the unique integer in the range [tex]0 \le a_k \le k-1[/itex] for which [itex]\displaystyle a_1 + a_2 + \cdots + a_k[/itex] is divisible by [itex]k[/itex]. For instance, when [itex]n = 9[/itex] the obtained sequence is [itex]\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots[/itex]. Prove that for any n the sequence [itex]\displaystyle a_1, a_2, a_3, \ldots[/itex] eventually becomes constant.
  2. jcsd
  3. Aug 15, 2007 #2
    that's cool, where'd you find this?
  4. Aug 16, 2007 #3
    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 [tex]{\sum}^k_{i=1}{a_i}=ck[/tex] 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 [tex]{\sum}^k_{i=1}{a_i}=ck[/tex] for some c<k.

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

    Then we have


    So by letting [tex]{n}\geq{\frac{k^{2}+k}{2}}[/tex] 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?
  5. Aug 16, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Aug 16, 2007 #5
    Aaah, I see what you mean. Thanks for the correction!
  7. Aug 16, 2007 #6
    haha, that's a usa math olympiad question. ah, reminds me of the good old days. looking forward to putnam in college
  8. Aug 16, 2007 #7
    define A(n) to be the least common multiple of the set {1,2,3...n}
    A(n) = {1,2,6,12,60,420,...}
    I noticed that if [tex]A_{m-1} < n \le A_{m}[/tex] then [tex]{\sum}^k_{i=1}{a_i} \geq \frac{kA_{m}}{m}[/tex] and [tex]a_{i}[/tex] converges to [tex]\frac{A_{m}}{m}[/tex] by the value of k equal to m. I thought I had a proof but need to come back to this later.
  9. Aug 16, 2007 #8
    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 :biggrin:
    http://www.artofproblemsolving.com/Wiki/index.php/2007_USAMO [Broken]
    Last edited by a moderator: May 3, 2017
  10. Aug 17, 2007 #9
    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 :rolleyes:
  11. Aug 17, 2007 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No you shouldn't. n is given to you in the question. k is what you play with.
  12. Aug 17, 2007 #11
    Yes, it turns out that all you need to work with is the k. However, I said this:

    That is clearly incorrect.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook