1. Limited time only! Sign up for a free 30min personal 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!

Pigeonhole Principle problem

  1. Mar 15, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove that there exists an integer divisible by 1989 Such that it's last four digits are 1990.

    2. Relevant equations
    Pigeonhole Principle where if we have k+1 items and k holes, two items go in one hole.


    3. The attempt at a solution

    Ok. I called my professor for help on this and I was given the hint that I should first take the integers from 1 to 1989, and multiply each one of them by 10^4. Then, when I divide each number, each has a different remainder, which means one of them has a remainder of one. I first need to figure out why this whole thing is true ( meaning why they each have different remainders). Then I need to figure out why it is important that one of these problems have a remainder of one. I have no clue on what to do here, so any suggestions would be great. Thanks for your time.
     
  2. jcsd
  3. Mar 15, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi philbein! :smile:
    Try adding 1989 to it :wink:
     
  4. Mar 15, 2009 #3
    Should I add 1989 to the remainder or to the orignal number that I had divided by 1989?
     
  5. Mar 15, 2009 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    erm :redface:

    if you're not sure, try both! :smile:
     
  6. Mar 15, 2009 #5
    I'm sorry. I'm still not seeing what this does. Either way, I am still left with a remainder of 1.
     
  7. Mar 15, 2009 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You've not quite got it right.

    The point is that you have numbers ending in 4 noughts, and when you add 1990 you have a number ending in 1990. You've just got to show...
     
  8. Mar 15, 2009 #7
    Ok. I'm still confused.
     
  9. Mar 15, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    What you actually want is an n such that n*10^4 has a remainder of 1988 when divided by 1989. Since 1990 has a remainder of 1. So sure, if you have the 1989 numbers n*10^4 for n=1...1989 and the remainders are all different and each remainder is in the range 0...1988, then one of them must be 1988. The pigeonhole principle is used in proving that the remainders are all different. Suppose n1*10^4 and n2*10^4 have the same remainder. That means (n1-n2)*10^4 is divisible by 1989, right? But 10^4 and 1989 are coprime. They have no common prime divisors. What does that tell you?
     
    Last edited: Mar 15, 2009
  10. Mar 16, 2009 #9
    Finally figured it out. Not an easy problem. Thanks for all the help. Couldn't have done it without the help. Thanks again.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Pigeonhole Principle problem
  1. Pigeonhole principle (Replies: 12)

  2. Pigeonhole problem? (Replies: 1)

  3. Pigeonhole Principle (Replies: 1)

Loading...