2 tough questions

  • Thread starter evanx
  • Start date
  • #1
4
0
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:

Answers and Replies

  • #2
mathwonk
Science Advisor
Homework Helper
11,063
1,254
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:
 
  • #3
740
13
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)
 
  • #4
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
 
  • #5
4
0
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).
 

Related Threads on 2 tough questions

  • Last Post
Replies
22
Views
3K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
21
Views
5K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
73
Views
6K
  • Last Post
Replies
7
Views
2K
Top