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.

Problem: In Duma, there are 1600 delegates, who have formed 16000 committees of 80 persons each. Prove that one can find two committees having at least four common members.

There is a probabilistic solution to this question, which I am having trouble following because I have no background in probability. It begins by calculating the expected number of common members of any two given committees and using this to find the solution. How exactly does this work?

I am also interested to know if anyone has a non-probabilistic solution.

Source: http://www.math.cmu.edu/~ploh/docs/math/mop2011/prob-method.pdf

EDIT: After further searching, I found the solution worked out in full detail on page 2 here: http://www.math.cmu.edu/~ploh/docs/math/mop2010/prob-comb-soln.pdf

share|improve this question
    
I'm not an expert on this, but I think a useful keyword is pairwise intersecting set systems/families. In short, you have a collection of $1600$ $80$-subsets of a big set of size $16000$, and you want to prove there exist two with intersection of at least $4$. Or, equivalently, the maximum size of any collection of $80$-subsets of a $16000$-set with this property is less than $1600$. –  TMM Nov 2 '12 at 21:20

1 Answer 1

up vote 2 down vote accepted

You can pose the same problem with just $800$ instead of $16000$ committees:

There are $16000\cdot 80$ committee memberships, hence by the pigeon-hole principle at least one delegate $A$ is in at least $800$ committees. (With just $800$ committees, we could only conclude that $A$ is in $40$ committees, but that is sufficient for the calculation below).

Assume that no committees with four or more common members exist. Then two of $A$'s committees have at most two other delegates in common. Thus $A$'s first committee gives us $79$ additional delegates, the second at least $79-2$ additional delegates, ..., the $n$th committee at least $79-2(n-1)$ additional delegates (per previous committee at most two delegates may already be "known"). Thus $40$ of $A$'s committees contain $$40\cdot 79-(0+2+4+\cdots+78)=1600$$ delegates apart from $A$. But then we'd have $1601$ delegates including $A$!

share|improve this answer
    
Can you say anything about the probabilistic solution? –  Potato Nov 2 '12 at 22:55

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.