2 tough questions

Please help me out!


Q1
m, n are natural numbers (which include zero for the sake of this question) and n =/= 0, then there are natural numbers q and r such that m= qn + r and r < n. Use the Well-Ordering Principle to prove this fact.

Q2
There are 51 students in a class. Prove there are at least two students with exactly the same number of friends.
 
Last edited:

mathwonk

Science Advisor
Homework Helper
10,616
810
the well orderin principle says there is a smallest number of a certain type. So in this problem look for the desired number which is supposed to be small. take all numbers like it and among them take the smallest one and see if it is small enough to work for you.

problem 2 is false without assuming each person has at least one friend. :grumpy:
 
what have you done so far? the first one is a pretty straightforward application of the wop. you've got a set of possible r's which is a subset of N... do i need to say the rest? then you need to show that the smallest element is the "right size", and that yer r & q are unique (uniqueness should be pretty routine, even for a beginner - it's done like every other uniqueness proof)
 
127
0
hmm... I think problem 2 is just fine without any added assumption. Well you have to assume friendship is mutual. If a is a friend of b then b is a friend of a. And no one is their own friend. But these are reasonable assumptions. So my two big hints are: 1)there is nothing special about 51, any number will do, and 2) the pigeon hole principle. So try the same question with 3,4,5 students.

Hope that helps,
Steven
 
fourier jr said:
what have you done so far? the first one is a pretty straightforward application of the wop. you've got a set of possible r's which is a subset of N... do i need to say the rest? then you need to show that the smallest element is the "right size", and that yer r & q are unique (uniqueness should be pretty routine, even for a beginner - it's done like every other uniqueness proof)
I have got Q2 (sort of...) but am at a loss for Q1 since I am unfamiliar with the Well-ordering principle. I do not have to prove uniqueness of r and q though (I think).
 

The Physics Forums Way

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