• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Pigeonhole Principle problem

  • Thread starter philbein
  • Start date
1. Homework Statement

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

2. Homework 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.
 

tiny-tim

Science Advisor
Homework Helper
25,790
246
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:
 
Should I add 1989 to the remainder or to the orignal number that I had divided by 1989?
 

tiny-tim

Science Advisor
Homework Helper
25,790
246
erm :redface:

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

matt grime

Science Advisor
Homework Helper
9,394
3
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...
 
Ok. I'm still confused.
 

Dick

Science Advisor
Homework Helper
26,258
618
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:
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 for: Pigeonhole Principle problem

  • Posted
Replies
1
Views
4K
Replies
2
Views
1K
  • Posted
Replies
12
Views
10K
Replies
13
Views
9K
Replies
8
Views
685

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top