1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
  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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Difficult Proof
  1. A Difficult Equation (Replies: 6)

  2. Difficult Problem (Replies: 15)

  3. A proof (Replies: 1)