1
$\begingroup$

From a group of $7$ persons, $7$ committees are formed. Any $2$ committees have exactly $1$ member in common. Each person is in exactly $3$ committees.

  1. At least $1$ committee must have more than $3$ members;
  2. Each committee must have exactly $3$ members;
  3. Each committee must have more than $3$ members;
  4. Nothing can be said about the sizes of the committees.

I used block designs. Using which I could prove that it is not possible for a committee to have 4 members .Which lead to me the answer that each committee must have exactly 3 members. However, I was looking to see if there existed a more formal approach for solving this.

My approach was just in case there are four members in the committee then they should each be in two more committees . If none of the two are in the same committee then this makes the number of committees to be 9. That will be in contradiction just seven committees existing . Hence there should be some committees such that two participants of the original four membered committee belong in them . Hence we come at a contradiction again.

$\endgroup$
  • $\begingroup$ What are your ideas? Did you do block designs? $\endgroup$ – Henno Brandsma Feb 21 '16 at 6:58
  • $\begingroup$ I did , do the block designs . Using which I could prove that it is not possible for a committee to have 4 members .Which lead to me the answer that each committee must have exactly 3 members. However, I was looking to see if there existed a more formal approach for solving this. $\endgroup$ – Noob101 Feb 21 '16 at 7:01
  • $\begingroup$ 4 members or more than 4 members too? $\endgroup$ – Henno Brandsma Feb 21 '16 at 7:02
  • 2
    $\begingroup$ My approach was just in case there are four members in the committee then they should each be in two more committees . If none of the two are in the same committee then this makes the number of committees to be 9. That will be in contradiction just seven committees existing . Hence there should be some committees such that two participants of the original four membered committee belong in them . Hence we come at a contradiction again. $\endgroup$ – Noob101 Feb 21 '16 at 7:04
  • $\begingroup$ So you already ruled out (a) and (c) using this reasoning. Add it to the question! It shows work done. Also, you ruled out (d) as well, come to think of it. $\endgroup$ – Henno Brandsma Feb 21 '16 at 7:12
1
$\begingroup$

To move the remarks to an answer: suppose some committee $c$ has at least $4$ different members $x_1,x_2,x_3,x_4$ from $\{1,\ldots,7\}$.

Then $x_i$ is also in two other committees, say $c^1_i, c^2_i$, where $c^1_i \neq c^2_i$ and $c^1_i \neq c, c^2_i \neq c$, for $i=1,\ldots,4$.

The set $\{c\} \cup \{c^j_i: i=1,\ldots,4; j=1,2\}$ has at most 7 members so the second set has coinciding members: there are $j,i,j',i'$ such that $c^j_i = c^{j'}_{i'} = c'$. We know that $i \neq i'$ and so we have that both $c$ and $c'$ have the members $x_i$ and $x_{i'}$ in common. This contradicts the assumptions.

(argument from OP, made a bit more formal).

This shows that (1) is false, no member can have more than 3 members. 3 is even more false, and 4 is false (we just said something about the size of the committees and proved it to boot). So 2 must be true by elimination.

Now find a block design on 7 points to show it is even possible to do it.

$\endgroup$

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.