Small Intersections

We assert that choosing all 0-element, 1-element, 2-element, and 3-element subsets results in maximal N. Clearly, such an arrangement fits the requirements of the question. Hence we assert that N is at most (1+11+55+165) = 232.

Note that because there are at most 2 shared elements between any two chosen subsets, hence for every subset with at least 3 elements, each triple of elements may only occur once. (For example, the triple {2, 5, 10} may only occur once within a subset; for if it occured in two different subsets, choosing these two subsets would result in more than 2 shared elements.) Hence, there may be at most 165 triples of elements among the subsets.

Next, we observe (for subsets with at least 3 elements) that a 3-element subset contains 1 triple, while a 4-element subset contains 4 triples, a 5-element subset contains 10 triples (and so on), and therefore if we wish to maximize the number of subsets, each subset must contain as little subsets as possible. Therefore, we choose all 165 3-element subsets.

Next, we also observe that adding subsets with 0, 1, or 2 elements does not break the requirements of the question; hence we choose these subsets as well. Therefore, maximal N is (1+11+55+165) = 232.

We are given that $|T_i∩T_j|≤2$ for all values $i≠j$ . In other words, all pairs of sets $T_i$ and $T_j$ have no 3-element subsets in common. For convenience, define $v(r)$ to be the number of 3-element subsets of the set $r$ .

Note that $v(S) = {11 \choose 3}=165$ . Thus, by the Pigeonhole Principle, we must have $\displaystyle \sum_{i=1}^N v(T_i) \leq 165$ for the conditions of the problem to hold.

To maximize $N$ , we observe that all subsets of $S$ with at most 2 elements have no 3-element subsets. Thus, we can let each of these subsets be a distinct $T_i$ , as they increase the value of $N$ without affecting the total number of 3-element subsets. We count these subsets of $S$ by the number of elements each set contains. There are ${11 \choose 0} + {11 \choose 1} + {11 \choose 2} = 1 + 11 + 55 = 67$ subsets of $S$ with at most 2 elements.

To count the number of sets $T_i$ that have 3 or more elements, we observe that the value of ${m \choose 3}$ , where $m \geq 3$ , is increasing with respect to integers $m$ . Therefore, we can maximize $N$ if each set $T_i$ has less elements. Thus, we let the distinct 3-element subsets of $S$ be different $T_i$ . There are $165$ such subsets, so we can not add any more subsets without violating the conditions of the problem.

Finally, we have found the $T_i$ that allow us to maximize $N$ while satisfying the condition in the problem. Adding our cases, the maximum value of $N$ is $67+165=\boxed{232}$

We can take all the distinct subsets of $S$ with $3$ or less elements, and no couple of them will have $3$ or more elements in common. Any bigger subset of $S$ will have three elements in common with one of the already taken $3$ -element subset.

Let's suppose that the configuration of subsets that gives the biggest $N$ has at least one subset with at least $4$ elements. Calling $A$ this subset we have that we can make $2$ subsets of $A$ , one made with the first, the second and the third element of $A$ (ordered from the smaller to the biggest), and the other made with the first, the second and the fourth element of $A$ . Substituting $A$ with these two subsets we get a configuration with more subsets where the requested property is still respected. But this is a contradiction as we were assuming that the previous configuration had the highest number of subsets.

Therefore the answer is:

$1+{11 \choose 1} + {11 \choose 2} + {11 \choose 3}=\fbox{232}$

First, we demonstrate that if we have optimized the number of subsets $N$ , then none of $\{T_i\}$ contain four or more elements. If we did have such a set with four elements, such as $\{1,2,3,4\}$ , then by the constraints of the problem, we cannot have the sets $\{1,2,3\}$ , $\{1,2,4\}$ , $\{1,3,4\}$ , and $\{2,3,4\}$ because each shares $3$ elements with $\{1,2,3,4\}$ . Thus, instead of including the four-element set, we can remove it and include the four three-element subsets, showing that $N$ could not have been optimized if some $T_i$ were a four-element subset. Similar logic shows that $T_i$ cannot have more than four elements. Thus, we conclude that the maximum number $N$ occurs when we take the empty subset, all one-element subsets, all two-element subsets, and all three-element subsets.

It is easily verified that no two of these sets can share three elements; otherwise, they must be the same three-element subset. The answer is thus ${11 \choose 0}+{11 \choose 1}+{11 \choose 2}+{11 \choose 3}=232$ .

Consider all subsets of $S$ that have 0, 1, 2 or 3 elements. They clearly satisfy the given conditions, and there are ${11 \choose 0} + { 11 \choose 1} + {11 \choose 2} + {11 \choose 3} = 1 + 11 + 55 + 165 = 232$ of them, so $N \geq 232$ .

Now, consider any set of subsets $T_1, T_2, \ldots T_N$ with $N$ maximum that satisfies the condition $| T_i \cap T_j | \leq 2$ for all values $i\neq j$ . If there exists a subset $T_i$ with $|T_i | \geq 4$ , let $C_1, C_2, \ldots, C_m$ denote all of its 3-element subsets, where $m = { |T_i| \choose 3} >1$ . $|C_i \cap C_j| \leq2$ since they are both distinct 3-element subsets. Since $C_k \subset T_i$ for all $k$ , it follows that $|C_k \cap T_j| \leq |T_i \cap T_j| \leq 2$ . This shows that we may replace $T_i$ with the the $m$ sets $C_k$ , and the condition still holds. Since $m>1$ and all the $C_k$ are distinct from the $T_j$ , this gives us even more sets, which contradicts the assumption that $N$ is maximal. Hence every subset $T_i$ satisfies $|T_i| \leq 3$ . Since there are 232 sets that satisfy this condition, $N \leq 232$ . Thus $N = 232$ .

Note: This solution naturally follows by studying the condition $| T_i \cap T_j | \leq 0$ for all values $i\neq j$ and $| T_i \cap T_j | \leq 1$ for all values $i = j$ .

total elements in the set S = 11

Number of subsets of S with number of elements equal to zero = 11C0 = 1

Number of subsets of S with number of elements equal to one = 11C1 = 11

Number of subsets of S with number of elements equal to two = 11C2 = 55

Number of subsets of S with number of elements equal to three = 11C3 = 165

Thus

Total numbers of subsets with number of elements equal to zero, one, two or three = 1+11+55+165 = 232

whish is required answer.

Now taking pairwise intersection of any two subsets of set S with at most three elements(where two subsets are not identical). we will have a set with at most two elements.

Otherwise if the result of intersection has three elements, this implies both the subset whose intersection is taken have same three elements, a condition which is not allowed as i≠j.

If $T_i$ has $4$ or more elements, there will exist other $T_j$ s with $3$ or $4$ elements which will be excluded as a result, so to achieve the highest possible $N$ we shall have no more than $3$ elements in each $T_i$ .

There are $C_3^{11}=165$ unique subsets with $3$ elements.

Likewise, there are $C_2^{11}=55$ unique subsets with $2$ elements, $C_1^{11}=11$ unique subsets with a single element.

Adding in the empty set, we get $N=165+55+11+1=232$