Pigeonhole Principle problem

  • Thread starter philbein
  • Start date
  • #1
9
0

Homework Statement



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

Homework Equations


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


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.
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,836
251
Hi philbein! :smile:
Then I need to figure out why it is important that one of these problems have a remainder of one.

Try adding 1989 to it :wink:
 
  • #3
9
0
Should I add 1989 to the remainder or to the orignal number that I had divided by 1989?
 
  • #4
tiny-tim
Science Advisor
Homework Helper
25,836
251
erm :redface:

if you're not sure, try both! :smile:
 
  • #5
9
0
I'm sorry. I'm still not seeing what this does. Either way, I am still left with a remainder of 1.
 
  • #6
matt grime
Science Advisor
Homework Helper
9,420
4
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...
 
  • #7
9
0
Ok. I'm still confused.
 
  • #8
Dick
Science Advisor
Homework Helper
26,263
619
Ok. I'm still confused.

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:
  • #9
9
0
Finally figured it out. Not an easy problem. Thanks for all the help. Couldn't have done it without the help. Thanks again.
 

Related Threads on Pigeonhole Principle problem

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
12
Views
11K
Replies
2
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
17
Views
8K
  • Last Post
Replies
8
Views
825
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
0
Views
2K
Top