Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

TuringTest

Let f be a function from the set of integers to the set of positive integers. Suppose that, for any two integers m and n, the difference\[f(m)−f(n)\]is divisible by\[f(m−n)\]Prove that, for all integers m and n with\[f(m)≤f(n)\]the number\[f(n)\] is divisible by \[f(m)\]

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. moneybird
    Best Response
    You've already chosen the best response.
    Medals 2

    \[\frac{f(m) - f(n)}{f(m-n)}=k\]Setting n = 0, \[f(m) | f(0)\]Setting m = 0, \[f(-n)| f(n)\]Setting m = 0, n = -n, \[f(n)| f(-n)\]\[f(n) = f(-n)\]Setting m = 2n, \[f(n) |f(2n)\]\[f(2n) \ge f(n)\]Setting n as -n \[f(m+n)|(f(m) - f(n))\]\[f(m) - f(n) \ge f(m+n)\] Assume \[f(m+n) > f(m)\], then\[f(m+n) > f(m) - f(n)\]However, this contradicts to \[f(m) - f(n) \ge f(m+n)\], which means \[f(m+n) \] is either smaller or equal to f(m). Assume \[f(m+n) < f(m)\]then setting m = n, \[f(2n) < f(n)\], which contradicts to \[f(2n) \ge f(n)\], Thus \[f(m+n) = f(m)\] Substitute this back to the original equation\[\frac{f(m+n)-f(n)}{f(m)}\]Thus, we proved \[f(m) | f(n)\]

    • 2 years ago
  2. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 0

    Wow moneybird this looks really great! I'll have to give it special attention on a non-holiday though, I don't think I'm smart enough to really evaluate it. Certainly not right now at least. I'll be sure to get others to look at this, this was an IMO problem, yeah?

    • 2 years ago
  3. moneybird
    Best Response
    You've already chosen the best response.
    Medals 2

    thanks

    • 2 years ago
  4. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 0

    Having had a bit more time to digest this I can say I follow the logic and see no mistakes. That said I don't think I'm qualified to give you the all clear myself. I'll be curious to hear other opinions. Again, excellent job!

    • 2 years ago
  5. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 2

    I don't see a problem

    • 2 years ago
  6. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 2

    though I would add more detail.

    • 2 years ago
  7. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 0

    like? what cases are not covered that should be?

    • 2 years ago
  8. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 2

    all the cases are covered...just more words to explain what is going on

    • 2 years ago
  9. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 0

    well he still deserves a medal then :)

    • 2 years ago
  10. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 2

    I don't like this sub forum...I'm only level 2 here :)

    • 2 years ago
  11. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 0

    there ya go! on the way to guru again.

    • 2 years ago
  12. JamesJ
    Best Response
    You've already chosen the best response.
    Medals 0

    Interesting proof, because it seems you've proven something stronger. When you get to the statement \[ f(m+n) = f(m) \] m and n are arbitrary, and hence f is constant.

    • 2 years ago
  13. asnaseer
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm not clear on how setting m=0 leads to:\[f(-n)| f(n)\]on the 5th line of the proof. same goes for the 7th line of the proof where setting m=0 and n=-n seems to lead to:\[f(n)| f(-n)\]how do we reach these conclusions?

    • 2 years ago
  14. moneybird
    Best Response
    You've already chosen the best response.
    Medals 2

    Actually I missed one step, which is setting m = -n and n equal to zero.\[\frac{f(-n)-f(0)}{f(-n)} \implies f(-n)| f(0)\]

    • 2 years ago
  15. asnaseer
    Best Response
    You've already chosen the best response.
    Medals 0

    is that a legal step? you are (in the same step) setting m=-n AND n=0. isn't that equivalent to setting m=0?

    • 2 years ago
  16. moneybird
    Best Response
    You've already chosen the best response.
    Medals 2

    This means that f(0) is divisible by f(-n). w When m = 0, \[\frac{f(0)-f(n))}{f(-n)} \implies f(-n) | f(n)\]

    • 2 years ago
  17. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 2

    you already had f(m)|f(0)...m was arbitrary...thus...

    • 2 years ago
  18. asnaseer
    Best Response
    You've already chosen the best response.
    Medals 0

    I understand the 1st step where you showed \(f(m)|f(0)\), but I am afraid I don't follow the rest of the arguments. this is probably beyond my expertise as I canot see how the next steps are deduced?

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.