2
$\begingroup$

A club with $x$ members is organized into four committees such that

$(a)$ each member is in exactly two committees,

$(b)$ any two committees have exactly one member in common.

Then $x$ has

$(A)$ exactly two values both between $4$ and $8$

$(B)$ exactly one value and this lies between $4$ and $8$

$(C)$ exactly two values both between $8$ and $16$

$(D)$ exactly one value and this lies between $8$ and $16$.

My thought is option $B$ and $x = 6$. Please somebody tell me am I right or wrong?

$\endgroup$
  • 1
    $\begingroup$ Can you show how you arrived at $x=6$? $\endgroup$ – RandomUser Apr 25 '14 at 16:53
  • 1
    $\begingroup$ I just see that if $x$=$6$ then the two conditions are satisfied.But if $x$<$6$ or $x$>$6$ the condition $b$ is not satisfied so I think $x$ may be $6$. $\endgroup$ – liesel Apr 25 '14 at 17:15
  • 1
    $\begingroup$ Please improve your title. $\endgroup$ – Alexander Gruber Apr 25 '14 at 17:22
3
$\begingroup$

Claim: $x=6$

Let $S:=[x]\left(=\{1,2,\dots ,x\}\right)$ where $x$ is some fixed natural number. Let $C_i\subset S$ be the $i$ th commitee.Let $f$ be a function from the set of unordered pair of distinct commitees to members of the club defined as, $$f\left( (C_i,C_j)\right)=C_i\cap C_j$$ $f$ is injective by (a). $f$ is surjective by (b).

Hence, $|S|=\binom{4}{2}=6$.


Here is a construction:

  • Let $C_1\cap C_2=1$ wlog. Then, $1\notin C_i \quad \forall \, i\in [4]\setminus \{1,2\}$.

  • Let $C_2\cap C_3=2$ wlog. Then, $2\notin C_i \quad \forall \, i\in [4]\setminus \{2,3\}$.

  • Let $C_3\cap C_4=3$ wlog. Then, $3\notin C_i \quad \forall \, i\in [4]\setminus \{3,4\}$.

  • Let $C_1\cap C_3=4$ wlog. Then, $4\notin C_i \quad \forall \, i\in [4]\setminus \{1,3\}$.

  • Let $C_1\cap C_4=5$ wlog. Then, $5\notin C_i \quad \forall \, i\in [4]\setminus \{1,4\}$.

  • Let $C_2\cap C_4=6$ wlog. Then, $6\notin C_i \quad \forall \, i\in [4]\setminus \{2,4\}$.

$\endgroup$
0
$\begingroup$

Let the committees be $A_1, A_2, A_3, A_4$ then $|A_1\cup A_2 \cup A_3 \cup A_4|=n$. There are $\binom{4}{2}=6$ pairwise intersections each of size $1$ and each intersection of triples must be empty since if not some member would belong to $3$ committees, a contradiction. If we make a $4 \times n$ table where rows are committees and columns are members and mark a $1$ whenever member $x_j$ belongs to committee $A_i$ we notice that the $i^{th}$ row sum is $|A_i|$ and the $j^{th}$ column sum is $2$ (since each member belongs to exactly $2$ committees) so equating row and column sums we get $\sum_{i=1}^{4}|A_i|= 2n.$

Putting this information together and using the inclusion-exclusion formula we get $n =6$

$\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.