1
$\begingroup$

There is given:

  • set $B=A_{1} \cup...\cup A_{n}$
  • $|A_{i}|=m_{i}$ for each $i$
  • every element of $B$ belongs to exactly $k$ sets $A_{i_{1}},...,A_{i_{k}}$

Calculate $|B|$ in terms of $m_{i}$. If it has not unique solution then find its upper bound.

I tried to use inclusion-exlusion principle but so far my estimation is too big. It is $m_{1}+...+m_{n}$

Is there any better estimations?

Regards.

$\endgroup$
  • $\begingroup$ Hint: If you union all of them you will have $k$ copies of every element. $\endgroup$ – G Aker Apr 24 at 9:20
2
$\begingroup$

Every element of $B$ belongs to exactly $k$ sets out of the $A_i$. So if we count all the elements of the $A_i$, we have counted each element of $B$ exactly $k$ times. This means that $$|A_1|+|A_2|+\cdots+|A_n|=k|B|.$$

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