4
$\begingroup$

Suppose $A_1, \ldots , A_6$ are six sets each with four elements and $B_1, \ldots, B_n$ are $n$ sets each with two elements. Let $S = A_1 \cup A_2 \cup \cdots \cup A_6 = B_1 \cup \cdots \cup B_n$. Given that each of the elements of $S$ belongs to exactly four of the $A$’s and to exactly three of the $B$’s, find n.

The first thing I tried is looking at cardinality because we are trying to prove equality by the axiom of extension. We have $\left | A_1 \cup A_2 \cup \cdots \cup A_6 \right| \leq 24$ and $\left |B_1 \cup \cdots \cup B_n \right | \leq 2n$. So let's suppose $\left |S \right| = m$ where $m \leq 2n$ and $m \leq 12$. I am trying to figure out how to utilize the last sentence . It seems if we can find $m$ we will be able to find $n$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Hint: We know that there are in total $6\cdot4=24$ (not necessarily different) elements in all A's together. (i.e. $\sum_{i=1}^6 |A_i|=24$) However, each element of $S$ appears in exactly four of the A's, so $S$ contains 6 elements. Now apply a similiar reasoning to the B's.

$\endgroup$
8
  • $\begingroup$ Thus $n = 9$ right? $\endgroup$ Feb 15, 2016 at 20:40
  • $\begingroup$ @user19405892 Correct. $\endgroup$
    – wythagoras
    Feb 16, 2016 at 8:04
  • $\begingroup$ How do we know there are $24$ elements in all A's together? its only the maximum value right and even if union of all A's together has $24$ elements can you explain how you concluded $S$ has $6$ elements $\endgroup$ Apr 27, 2017 at 2:00
  • $\begingroup$ @Umeshshankar I mean that there are $6 \cdot 4 = 24$ not-necessarily different values in all $A$s together, before taking the union. Since since each element of $S$ appears in exactly 4 $A$s (given), $S$ contains $\frac{24}{4} = 6$ elements. $\endgroup$
    – wythagoras
    Apr 27, 2017 at 7:02
  • 1
    $\begingroup$ I am going to quibble that "We know that there are in total 24 elements in all A's together" was improperly and ambiguous and not actually correct. I believe stating it as "there are 24 instances of element representation in the 6 sets and each distinct element has 4 instances of representation, so there are 6 distinct elements" might (or might not) be a more accurate attempt. (Although I freely acknowledge its not without its own problem-- obtuse and pompous wording for one.) $\endgroup$
    – fleablood
    Apr 28, 2017 at 19:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .