2
$\begingroup$

(Yufei Zhao) Twenty-five people form some committees with each committee has 5 members and each pair of committees have at most one common member. Determine, with justification, the maximum number of committees.

My approach: Let $m$ be the maximum number of committees. If there are more than 7 committees, then the number of duplicates is at most $\frac{m(m-1)}{2}$ but then I'm stuck. I'm guessing the answer is 10.

Am I right? Am I on the right track? Can you give me a hint if I'm not?

$\endgroup$
4
$\begingroup$

Each committee has $\binom{5}2=10$ pairs of people. No two committees contain the same pair of people. Since there are only $\binom{25}2=300$ pairs total, there can be at most $300/10=30$ committees.

This can be accomplished using the affine plane of order $5$. Identify the people with the set of order pairs $(x,y)$ for $x,y\in \mathbb Z/\mathbb 5\mathbb Z$. The committees are the set of "lines" over $\mathbb Z/\mathbb 5\mathbb Z$, where there $25$ lines of the form $L_{m,b}=\{(x,mx+b)\mid x\in \mathbb Z/\mathbb 5\mathbb Z\}$, where $m,b\in \mathbb Z/\mathbb 5\mathbb Z$, and $5$ vertical lines of the form $V_x=\{(x,y)\mid y\in \mathbb Z/\mathbb 5\mathbb Z\}$ for $x\in \mathbb Z/\mathbb 5\mathbb Z$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much! That is some great insight! $\endgroup$ – Kai Jun 4 '19 at 23:26

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.