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

  • $\begingroup$ 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$. $\endgroup$ – TMM Nov 2 '12 at 21:20

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$!

| cite | improve this answer | |
  • $\begingroup$ Can you say anything about the probabilistic solution? $\endgroup$ – Potato Nov 2 '12 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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