# Maximum number of sets given rules

In the collection of sets under consideration, the following rules apply:

(1) Each set in the collection has $n$ elements;

(2) The pairwise intersection of any 2 distinct sets in the collection has exactly one element;

(3) The intersection of any 3 distinct sets is empty.

What is the maximum number of sets in the collection? I've tried figured out the answer for $n=2,3,4$ by brute force, but I am not sure what the general principle I should use to solve this.

• Are you sure that is all the information. The number of sets is unlimited. Nov 6, 2017 at 0:39
• I think he is asking the maximum number of sets for a given n Nov 6, 2017 at 0:40
• Oh..... That would make a lot more sense. Nov 6, 2017 at 0:41
• @QthePlatypus yes, obviously you are right. Nothing says there are $n$ sets..... Nov 6, 2017 at 0:42
• Yes, $n$ is fixed in the question.
– Paul
Nov 6, 2017 at 0:46

The maximum will be $n+1$.

If there were more than $n+1$ sets then for any specific set $A$ there will be at least $n +1$ pairs of sets where $A$ is one of them. $A$ will need a distinct element for each of those pairs so $A$ will have at least $n+1$ distinct elements violating condition $1$.

So the maximum is $\le n+1$.

$n+1$ is possible. There will $n$ pairs for $A$. Those can be the disinct elements of $A$.

If you need a concrete example: Let each $A_i$ be a set of unordered pairs. I.e. sets of two numbers where order doesn't matter so $\langle a, b\rangle$ is considered to be the same as $\langle b, a\rangle$

Let $A_i = \{ \langle i, j\rangle| j \le n+1; j\ne i\}$. i.e. the set of all pairs containing $i$ (pairs of distinct numbers within a range of $1$ to $n+1$ of with $i$ is one of the pair).

Then $A_i \cap A_j = \{ \langle i, j\rangle\}$ but $\{\langle i, j\rangle\}$ will not be in any other $A_k$. (as $i \ne k, j\ne k$).

If that's too vague:

Let $p_i =$ the $i$-th prime.

Let $A_k = \{p_i*p_k|i \le n+1, i \ne k\}$.

Then each $A_k$ will have $n$ composite numbers as elements. If $i \ne j$ then $A_k \cap A_j = \{p_k*p_i\}$. This number $p_k*p_i$ will not be in any other set than those two as $p_kp_i$ has no other prime factors. So all conditions are met.

• Yes, thanks, although I realize I need to ask a modified question to get at what I wanted.
– Paul
Nov 6, 2017 at 1:18
• You use $(i,j)$ in one case but $\{i,j\}$ in another since ordered pairs have order it will not work quite the way you want. Nov 6, 2017 at 1:19
• Right. I didn't mean to type those as ordered pairs. Because order does not matter. That was a typo. They are sets with two elements. Unordered pairs, as it were. Nov 6, 2017 at 1:21
• Unordered pairs. It's not that hard a concept...... Nov 6, 2017 at 1:27

If we think of the number of sets in the system as $m$ then each set will need $m - 1$ elements that it uniquely shares with another set. So $m = n + 1$.

Here is a "proof by construction". First of all, notice that there cannot be more than $n+1$ sets in the collection: if a set with $n$ elements intersects more than $n$ sets, then at least three sets will intersect, contradicting (3).

To create a collection with $n+1$ sets satisfying (1)-(3), you may begin with $A_1 = \{1,2,\dots,n\}$. Let $A_2$ share the number 1 with $A_1$, and then fill it up with new unused numbers: $A_2 = \{1,n+1,n+2,\dots,2n-1\}$. Let $A_3$ share the number 2 with $A_1$ and the number $n+1$ with $A_2$, and then fill it up. Continuing like this, you will in each step add a set to the collection so that (1)-(3) are satisfied. This process will clearly end when we got a total of $n+1$ sets.