Help Me Out With These 2 Tough Questions

[evanx]

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.

 

[mathwonk]

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:

 

[fourier jr]

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)

 

[snoble]

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

 

[evanx]

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).