Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
