2
$\begingroup$

We have a set which has $20$ elements (eg. $\{1,2,3,...,20\}$). We want to choose the maximum number of non-empty subsets we can such that none of them has more than 2 common elements. for example $\{1,2,3,4,5\},\{1,2,3,6,7,8\}$ Has three common elements. For better clarification, if we wanted to solve this problem for $4$ instead of $20$ then the best way is to choose all the subsets except the $\{1,2,3,4\}$ so the answer in this way is $15-1 = 14$.

At first, it is obvious that all 1-element subsets and 2-element subsets can be choosed. So if we name the answer $A$ then $A>C(20,1) + C(20,2)$. But I am not sure what to do after that. For example I can say we can choose all the 3-element subsets and there will be no problem but we can not choose any other subset if we choose all 3-element subsets. So I don't know whether there is a way to not choose some of 3-element subsets and choose larger-sized subsets such that the answer gets bigger or not.

Note that we don't want to count all the possible ways. We want to find the best way to choose the maximum number of subsets we can that satisfy the condition. And we want to find this maximum number.

I must add that maybe the question can be solved for $n$ instead of $20$. But I was not sure whether there is a specific answer for the general form of the question. So, I used $20$ instead.

Sorry for my English. If the question is not clear, feel free to ask for clarification.

$\endgroup$
5
$\begingroup$

Let $[20]=\{1,2,3,\dots,20\}$ and suppose $S$ is a family of subsets of $[20]$ such that no two elements of $S$ have more than two elements in common.

For each set $X\in S$ let $X'=X$ if $|X|\le3$, otherwise let $X'$ be some $3$-element subset of $X$. Let $S'=\{X':X\in S\}$. Then $S'\subseteq\{X\subseteq[20]:|X|\le3\}$. Since the map $X\mapsto X'$ is injective, $$|S|=|S'|\le\binom{20}0+\binom{20}1+\binom{20}2+\binom{20}3=1351$$ so tha maximum is $1351$.

Well, $1351$ is the answer to your title question where you just wanted "subsets". For your body question, where you threw in "non-empty" for some reason, the answer is of course one less.


P.S. Here is a proof of the fact that the map $X\to X'$ defined above is injective. Suppose $X,Y\in S$ and $X'=Y'$; I have to show that $X=Y$.

If $|X'|=|Y'|\le2$, then $X'=X$ and $Y'=Y$, so $X=Y$.

If $|X'|=|Y'|=3$, then, since $X'\subseteq X$ and $Y'\subseteq Y$, we have $X'=Y'\subseteq X\cap Y$, so $|X\cap Y|\ge3$. Since two different elements of $S$ can have at most two elements in common, this means that $X=Y$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. But I didn't completely understand why this answer is maximum. How can I say that we cannot omit some of 3-element subsets and add 4-element subsets such that the answer gets larger? Maybe I didn't completely understand why X↦X′ is injective. $\endgroup$ – amir na Feb 17 at 9:17
0
$\begingroup$

You can choose all subsets of size $3$ as well, so the lower bound becomes ${20 \choose 1}+{20 \choose 2}+{20 \choose 3}$.

$\endgroup$
  • $\begingroup$ You can choose the empty set too, so the maximum is $\binom{20}0+\binom{20}1+\binom{20}2+\binom{20}3$. $\endgroup$ – bof Feb 16 at 23:50
  • $\begingroup$ @bof: OP said nonempty subsets. I just wonder if we could pick some other size than three and have all the intersections two. $\endgroup$ – Ross Millikan Feb 17 at 0:00
  • $\begingroup$ I see. OP omitted "nonempty" from the title. $\endgroup$ – bof Feb 17 at 0:09

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.