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.

There are $p$ committees in a class (where $p \ge 5$), each consisting of $q$ members (where $q \ge 6$).No two committees are allowed to have more than 1 student in common. What is the minimum and maximum number of students possible?

It is easy to see that the maximum number of student is $pq$,however I am not sure how to find the minimum number of students.Any ideas?

ADDED I am adding the given answer options:

$1) \quad pq - \binom{q}{2}$

$2) \quad pq - \binom{p}{2}$

$3) \quad (p-1)(q-1)$

share|improve this question
1  
Something is missing. Is every student supposed to be on a committee? –  JavaMan Aug 31 '11 at 16:24
    
@DJC:Not mentioned in the question,I guess we may have to consider that to get a solution. –  Quixotic Aug 31 '11 at 16:28
    
@DJC: For the minimum number of students this does not matter. –  TMM Aug 31 '11 at 16:30
    
@Thijs Laarhoven:Yes you are right but as the problem also asked for maximum number I have considered it in my solution. –  Quixotic Aug 31 '11 at 16:31
    
@Thijs, FoolForMath, I guess my question is, should the minimum answer be in terms of $p$ and $q$? –  JavaMan Aug 31 '11 at 16:31

6 Answers 6

up vote 3 down vote accepted

For $1\leq i\leq p$, let $C_i$ be the set of students on the $i$th committee. Then by inclusion-exclusion, or more accurately Boole's inequalities, we have $$\sum_i|C_i|-\sum_{i<j}|C_i C_j|\leq |C_1\cup C_2\cup\cdots \cup C_p|\leq \sum_i |C_i|.$$

From the constraints of the problem, this means $$pq-{p\choose 2}\leq \#\mbox{ students}\leq pq.$$

share|improve this answer
    
What is $j$ here?and I can't relate this with your answer. –  Quixotic Sep 1 '11 at 7:25
    
$j$ is also a generic index that runs from $1$ to $p$. The inequalities are also known as Bonferroni inequalities (planetmath.org/encyclopedia/BonferroniInequalities.html), and can apply to cardinalities instead of probabilities. –  Byron Schmuland Sep 1 '11 at 14:10

I think the following theorem might be relevant:

Theorem. Let $\mathcal{F}$ be a family of subsets of $\{1, \dots , n \}$ with the property that $|A \cap B| = 1$ for all $A,B \in \mathcal{F}$. Then $|\mathcal{F}| \leq n$.

Also this theorem could be relevant as well.

share|improve this answer

For the case in which $p \le q+1$ an arrangement that yields the minimum number of students can be described as follows.

Let $P = \{\langle m,n \rangle:1 \le m \le p, 1 \le n \le q+1\}$, and let $S = \{\langle m,n \rangle \in P:m < n\}$. If $P$ is thought of as a $p \times (q+1)$ grid, $S$ is the part of it strictly above the main ‘diagonal’. The cells in $S$ are the students; the $k$-th committee consists of those cells in $S$ that are either in row $k$ or in column $k$. More formally, for $1 \le k \le p$ let $$\begin{align*}C_k &= \{\langle m,n \rangle \in S:m=k \lor n=k\}\\ &= \{\langle k,n \rangle:k+1 \le n \le q+1\} \cup \{\langle m,k \rangle:1 \le m \le k-1\};\end{align*}$$ clearly $\vert C_k \vert = q+1-k+k-1=q$, and if $1 \le i < k \le p$, $C_i \cap C_k = \{\langle i,k \rangle\}$. Since every pair of committees shares a different student, this arrangement must minimize the number of students, so we need only calculate $\vert S \vert$.

Columns $2$ through $p$ of the grid contain $\sum_{k=1}^{p-1} k = \binom{p}{2}$ cells, and the remaining $q+1-p$ columns contain $p(q+1-p)$ cells, so $$\begin{align*}\vert S \vert &= \binom{p}{2} + p(q+1-p)\\ &= \frac{p^2 - p}{2} + pq + p - p^2\\ &= pq - \frac{p^2-p}{2}\\&= pq - \binom{p}{2}. \end{align*}$$

When $p > q+1$ the same approach works, but it’s no longer possible to get every pair of committees to overlap. First form $\left\lfloor \frac{p}{q+1}\right\rfloor$ sets of $q+1$ committees each. Each set requires $(q+1)q-\binom{q+1}{2}=\binom{q+1}{2}$ students, and committees in different sets must be disjoint, so this accounts for $\left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2}$ students. The remaining $r = p-(q+1)\left\lfloor \frac{p}{q+1}\right\rfloor$ committees will then require another $rq - \binom{r}{2}$ students, for a grand total of $$\begin{align*} \vert S \vert &= \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} + rq - \binom{r}{2}\\ &= \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} + \left(p-(q+1)\left\lfloor \frac{p}{q+1}\right\rfloor\right)q - \binom{r}{2}\\ &= pq - \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} - \binom{r}{2} \end{align*},$$ which does not appear to simplify greatly.

I see that this is essentially Alex’s solution, but expressed a little more concretely.

share|improve this answer

Alright, my guess is the question is saying, for some fixed value of $p$ and $q$, what is the maximum and minimum number of students we can have. If so, I agree the maximum number is $pq$, as we just don't let any of the students overlap in any committees. It's also been awhile since I've done anything like this, so hopefully I'm not making a silly mistake!

For the minimum, you want to maximize the overlap. Lets start with the simplest(?) case, where $p=5$ and $q=6$. Call the committees $p_1,\ldots,p_5$. The maximum overlap that can occur, is 4 students from one committee each being members of the other 4 committees, hence with the maximum overlap possible, the number of students we require is \begin{align*} 30 - 4 - 3 - 2 - 1 = 20. \end{align*}

What if we change $q = 7$? Nothing changes, as the committees have overlapped as much as possible already, so for any $q \geq 6$, the number of students is \begin{align*} pq - \sum_{i=1}^{p-1} i = pq - \frac{p(p-1)}{2}. \end{align*}

Of course this only "half" of what we want. What if we leave $q$ at 6, but set $p=6$? Now there is an entire other committee where we can overlap students, so we overlap as many more as possible, we get that the minimum number of students required is \begin{align*} 36 - 5 - 4 - 3 - 2 - 1 = 21. \end{align*}

As the number of committees increases, we may be able to overlaps more students. Suppose $p=7$ and $q=6$. We find the minimum number of students required is \begin{align*} 42 - 6 - 5 - 4 - 3 - 2 - 1 = 21. \end{align*} The same as above! But if we add one more committee, we cannot overlap any of the present students, so we must have another $q$ added in. In general, set $m = \lfloor p/(q+1) \rfloor$. We require, minimally \begin{align*} m\left(q(q+1) - \sum_{i=1}^q i\right) + \left(rq - \sum_{i=1}^{r-1} i\right) \end{align*} students, where $r$ is the remainder when $p$ is divided by $q+1$. Of course, the sums can be evaluated to give you an expression without the $i$'s if you'd like.

share|improve this answer
    
In the derivation,\begin{align*} pq - \sum_{i=1}^{p-1} i = pq - \frac{p(p+1)}{2}. \end{align*} you probably meant $pq - \frac{p(p-1)}{2}$ –  Quixotic Aug 31 '11 at 21:05
    
Oop! Definitely. –  Alex Aug 31 '11 at 21:16

This sounds like a test question where we want a quick solution. Given the choices, we can consider asymptotics. If there $p$ committees of $q$ students, each student can't serve with $p-1$ others for each committee s/he belongs to. It has to be of order $pq$, not $p^2$ or $q^2$, so must be $(p-1)(q-1)$

share|improve this answer

Here is a lower bound from a standard double counting argument. Let the number of students be $n$. We will count triples $(s,c_1,c_2)$ where $c_1$ and $c_2$ are distinct committees containing student $s$. Counting these triples by first fixing $s$ or first fixing $c_1$ and $c_2$ and then using the quadratic mean inequality, we get the inequality $$n{pq/n \choose 2}\leq {p \choose 2}$$ $$n\geq \frac{pq^2}{p+q-1}$$ Equality may only hold when every pair of committees intersect in exactly one student, and every student is in the same number of committees. These are block designs with $\lambda=1$. When $n=p$, these are projective planes. Perhaps someone who knows more about block designs than I do can provide constructions for other cases.

share|improve this answer

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.