Show that $n ≤ 100$ if $ \{A_1,A_2,... ,A_n\}$ is a set of distinct $3$-element subsets of $\{1, 2,... , 36\}$ such that...

Question

Let $X = \{A_1,A_2,... ,A_n\}$ be a set of distinct $3$-element subsets of $\{1, 2,... , 36\}$ such that

i) $A_i$ and $A_j$ have non-empty intersection for every $i,j$.

ii) The intersection of all the elements of $X$ is the empty set.

Show that $n ≤ 100$. How many such sets $X$ are there when $n = 100$?

Source: BMO 2005 round 2 question.

Please help !! I am not even able to proceed with the question I tried to come up with a recurrence relation but its not working. I have only been able to figure out the number when 36 is replaced by 6, which is an easy thing to do

Answer 1

I think I've made some progress with this, but I still haven't solved it. I believe that the problem is a special case of this theorem (which I can't prove yet):

Let $N\ge7$ and let $X = \{A_1,A_2,... ,A_n\}$ be a family of $3-$subsets of $[N]=\{1,2,\dots,N\}$ such that

i) $A_i\cap A_j=\emptyset$ for $i\ne j$

ii) $\displaystyle{\bigcap_{i=1}^nA_i}=\emptyset$

Then $n\leq3N-8.$

Furthermore, I believe that, under the same hypotheses, every family of length $3N-8$ belongs to one of the two classes defined below. In what follows, $a,b,c,d$ represent pairwise distinct integers between $1$ and $N$.

Class A is the set of all $3-$subsets of $[N]$ of one of the forms $\{a,b,x\},\ \{a,c,x\},\ \{b,c,x\}.$

Class B is the set of all $3-$subsets of $[N]$ that is either $\{a,b,c\}$ or of one of the forms $\{a,d,x\},\ \{b,d,x\},\ \{c,d,x\}.$

It's easy to verify that both classes satisfy the requirements and clear that there are ${N\choose3}$ families in class A and $N{N-1\choose3}$ families in class B.

I've written a python script to verify this for $N=7$ and $N=8.$ It would probably take too long to run for $N=9.$ For $N=6$ the maximum length is $10$ as expected, but there are $1018$ families.

I've been trying to prove this by induction, though I don't see how to do the basis case without a computer. Since we can produce a family of size $3N-8$ we suppose that we have some larger family. What I want to say is that there must be some element of $[N]$ that belongs to at most $3$ of the $3-$subsets. (This is true for families of class A and B.) We can assume that this element is $N$. Removing all the $3-$subsets containing $N$ would give a family of $3-$subsets of $[N-1]$ with too many elements. I'm also hopeful that since we know that a maximum-length family of $3-$subsets of $[N-1]$ is of class A or class B, we can infer that the family formed by adding no more than $3$ subsets containing $N$ is also of one of these forms.

If this approach is to work, we must prove that there is no family $X$ satisfying the requirements such that every element of $[N]$ belongs to at least $4$ members of $X.$ So far, I don't even know how to approach this.

Here is my python script, if anyone is interested.

'''
What is the largest family of 3-subsets of {1,2,...,N} such that
any two of them intersect, but no element is in all of them?
Find all such families.

The set of all 3-subsets containing at least 2 elements of {1,2,3}
satisfies the conditions and has 3N-8 elements, so this is a 
lower bound.
'''
from itertools import combinations

def expected(N):
    # binomial(N,3) + N*binomial(N-1,3)
    return N*(N-1)*(N-2)**2//6

N = 8
U= list(combinations(range(1,N+1),3))
highWater = 3*N-8    
S = { }  #S[k] = set of possible 3-subsets at level k
a = { }   # current solution
join ={0:list(range(1,N+1))}   #join[k] is intersection of a[1],...,a[k] 
k = 1
S[1] = U
solutions = list()
while k > 0:
    while S[k]:
        a[k] = S[k].pop(0)
        join[k] = [x for x in a[k] if x in join[k-1]]
        if not join[k]:
            if k==highWater: 
                solutions.append(list(a.values()))
            elif k > highWater:
                solutions.clear()
                highWater=k
                solutions.append(list(a.values()))
        k += 1
        S[k] = [s for s in S[k-1] if set(s) & set(a[k-1])] 
    k = k-1  # backtrack
        
print(N, "max length", highWater, len(solutions), "families", 
         expected(N), "expected") 

    
    

Answer 2

Here is a big case analysis. I haven't worked out how many such sets there are, though it is probably not too hard to figure out.

Assume $n\geq 100.$ Since $300>288=8*36$ some number $i$ is used by at least nine of the sets $A_j.$ We can assume it's $1.$ Let $I$ be the intersection of all the sets $A_j$ that don't include $1$ (using the fact that there must be at least one such set). Now split by cases on the order of $I.$

Case 1. $|I|=3.$

In this case, there is a single set not using $1,$ which we can assume is $\{2,3,4\}.$ All other $A_j$ are of the form $\{1,x,y\}$ with $x\in\{2,3,4\}.$ There are three of these with $y\in\{2,3,4\}$ and $3*32=96$ with $y\not\in\{2,3,4\},$ plus the $\{2,3,4\},$ giving 100 total.

Case 2. $|I|=2.$

We can assume that the sets not including $1$ are precisely $\{2,3,x\}$ for $x\in \{4,\dots,k\}$ with $k>4.$

Assume for now that no $A_j$ is equal to $\{1,4,5\}$ (which could happen if $k=5.$) Then all sets including $1$ must be of the form $\{1,2,y\}$ or $\{1,3,y\}$ for some $y,$ because they need to intersect all the sets $\{2,3,x\}.$ This gives one set of the form $\{1,2,3\}$ and $2*33=66$ others including 1, and 33 sets not including 1. So 100 total.

In the special case that $k=5$ and some $A_j$ equals $\{1,4,5\},$ there is one more set, but none of the sets $\{1,2,y\}$ and $\{1,3,y\}$ can be included. So there are hardly any sets in that case, certainly much less than 100.

Case 3. $|I|=1.$

We can assume every set not including 1 contains 2.

The first sub-case is that two triples not including 1 have an intersection of order 1, $\{2,3,4\}$ and $\{2,5,6\}$ say. Then every set containing 1 that does not hit 2 must hit 3 or 4 as well as 5 or 6. Furthermore some set doesn't contain 2 so must be $\{1,3,5\}$ (swapping 3 and 4 if necessary, and 5 and 6 if necessary). If none of the sets $\{1,3,6\},\{1,4,5\},\{1,4,6\}$ are in the family, there are $34 + 1$ sets that include 1, and 65 not including 1 because these must contain 2 and either 3 or 5. This gives 100. If one of the sets $\{1,3,6\},\{1,4,5\},\{1,4,6\}$ is in the family, then there are much fewer sets containing 2, so much fewer than 100 total.

The other sub-case is that all triples containing $2$ have an intersection of order 2. We can assume $\{2,3,4\}$ is in the family, then a set not containing 4, say $\{2,3,5\},$ and a set not containing 3, which must be $\{2,4,5\},$ and there are no other sets not containing 1. There are then just not enough sets containing 1: at most 34 containing 1 and 2, and at most three others.

Case 4. $|I|=0.$

The first sub-case is that two triples not including 1 have an intersection of order 1, $\{2,3,4\}$ and $\{2,5,6\}$ say. There is another set not including 2, say $\{3,5,x\}$ with $x\neq 2.$ There are then at most seven sets including 1 - $\{1,2,3\},\{1,2,5\},\{1,2,x\},\{1,3,5\},\{1,3,6\},\{1,4,5\},\{1,4,6\}$ - contradicting the assumption that 1 is in at least nine sets.

The other sub-case is that all triples not containing 1 have an intersection of order 2. We can assume $\{2,3,4\}$ is in the family, then a set not containing 4, say $\{2,3,5\},$ and a set not containing 3, which must be $\{2,4,5\},$ and then $\{3,4,5\}.$ Again there are then just not enough sets containing 1: at most $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\}.$