3
$\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$
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$
  • $\begingroup$ Thus $n = 9$ right? $\endgroup$ – user19405892 Feb 15 '16 at 20:40
  • $\begingroup$ @user19405892 Correct. $\endgroup$ – wythagoras Feb 16 '16 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$ – Umesh shankar Apr 27 '17 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 '17 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 '17 at 19:59

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.