Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a discrete math question here but im not sure how to approach it with inclusion-exclusion. Can someone help me out?

Consider a party of 60 persons. Assume that each person knows more than m other persons.

(a) How large must m be to guarantee that 3 persons know each other? Hint: use inclusion-exclusion on two sets as in the class example (see notes)

(b) How large must m be to guarantee that 4 persons know each other? Hint: use inclusion-exclusion on two sets as in part (a) to establish a lower bound on the size of the intersection, then use inclusion-exclusion again on that intersection and another set

share|improve this question
3  
Given that we don't have the class example or the class notes, it is somewhat difficult to help you use the hint... –  Arturo Magidin Mar 23 '12 at 16:05
    
This question is very similar to your other one ( math.stackexchange.com/questions/123646/… ), how far do you get considering the solution of the other question? –  Listing Mar 23 '12 at 17:11
    
Are you supposed to assume knowing is a reflexive relation, i.e. that if $A$ knows $B$ then $B$ knows $A$? –  Robert Israel Mar 23 '12 at 21:50
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.