1
$\begingroup$

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.

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

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Yes, thanks, although I realize I need to ask a modified question to get at what I wanted. $\endgroup$
    – Paul
    Nov 6, 2017 at 1:18
  • $\begingroup$ 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. $\endgroup$ Nov 6, 2017 at 1:19
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Nov 6, 2017 at 1:21
  • $\begingroup$ Unordered pairs. It's not that hard a concept...... $\endgroup$
    – fleablood
    Nov 6, 2017 at 1:27
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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