Demuestra que $n ≤ 100$ si $ \{A_1,A_2,... ,A_n\}$ es un conjunto de $3$ -subconjuntos de elementos de $\{1, 2,... , 36\}$ tal que...

Question

Sea $X = \{A_1,A_2,... ,A_n\}$ sea un conjunto de $3$ -subconjuntos de elementos de $\{1, 2,... , 36\}$ tal que

i) $A_i$ y $A_j$ tienen intersección no vacía para cada $i,j$ .

ii) La intersección de todos los elementos de $X$ es el conjunto vacío.

Demuestra que $n 100$ . ¿Cuántos conjuntos de este tipo $X$ están ahí cuando $n = 100$ ?

Fuente: Pregunta de la ronda 2 de BMO 2005.

Por favor, ¡ayuda! Ni siquiera soy capaz de continuar con la pregunta. He intentado establecer una relación de recurrencia pero no funciona. Sólo he sido capaz de averiguar el número cuando 36 se sustituye por 6, que es una cosa fácil de hacer

Answer 1

Creo que he hecho algunos progresos con esto, pero todavía no lo he resuelto. Creo que el problema es un caso especial de este teorema (que aún no puedo demostrar):

Sea $N\ge7$ y que $X = \{A_1,A_2,... ,A_n\}$ sea una familia de $3-$ subconjuntos de $[N]=\{1,2,\dots,N\}$ tal que

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

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

Entonces $n\leq3N-8.$

Además, creo que, bajo las mismas hipótesis, cada familia de longitud $3N-8$ pertenece a una de las dos clases definidas a continuación. En lo que sigue, $a,b,c,d$ representan números enteros distintos por pares entre $1$ y $N$ .

La clase A es el conjunto de todos los $3-$ subconjuntos de $[N]$ de una de las formas $\{a,b,x\},\ \{a,c,x\},\ \{b,c,x\}.$

La clase B es el conjunto de todos los $3-$ subconjuntos de $[N]$ que sea $\{a,b,c\}$ o de una de las formas $\{a,d,x\},\ \{b,d,x\},\ \{c,d,x\}.$

Es fácil comprobar que ambas clases satisfacen los requisitos y está claro que hay ${N\choose3}$ familias de clase A y $N{N-1\choose3}$ familias de la clase B.

He escrito un script en python para verificar esto para $N=7$ y $N=8.$ Probablemente tardaría demasiado en funcionar para $N=9.$ Para $N=6$ la longitud máxima es $10$ como se esperaba, pero hay $1018$ familias.

He estado intentando demostrar esto por inducción, aunque no veo cómo hacer el caso base sin un ordenador. Dado que podemos producir una familia de tamaño $3N-8$ suponemos que tenemos una familia más grande. Lo que quiero decir es que debe haber algún elemento de $[N]$ que pertenezca como máximo a $3$ de la $3-$ subconjuntos. (Esto es cierto para las familias de clase A y B.) Podemos suponer que este elemento es $N$ . Eliminación de todos los $3-$ subconjuntos que contienen $N$ daría a una familia de $3-$ subconjuntos de $[N-1]$ con demasiados elementos. También tengo la esperanza de que como sabemos que una familia de longitud máxima de $3-$ subconjuntos de $[N-1]$ es de clase A o de clase B, podemos deducir que la familia formada añadiendo no más de $3$ subconjuntos que contienen $N$ también es de una de estas formas.

Para que este planteamiento funcione, debemos demostrar que no existe una familia $X$ que cumpla los requisitos de forma que cada elemento de $[N]$ pertenece al menos a $4$ miembros de $X.$ Hasta ahora, ni siquiera sé cómo enfocar esto.

Aquí está mi script en python, por si a alguien le interesa.

'''
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

He aquí el análisis de un gran caso. No he calculado cuántos conjuntos de este tipo hay, aunque probablemente no sea muy difícil de averiguar.

Supongamos que $n\geq 100.$ Desde $300>288=8*36$ algún número $i$ es utilizado por al menos nueve de los conjuntos $A_j.$ Podemos suponer que es $1.$ Sea $I$ sea la intersección de todos los conjuntos $A_j$ que no incluyen $1$ (utilizando el hecho de que debe existir al menos un conjunto de este tipo). Ahora dividimos por casos del orden de $I.$

Caso 1. $|I|=3.$

En este caso, hay un único conjunto que no utiliza $1,$ que podemos suponer que es $\{2,3,4\}.$ Todos los demás $A_j$ son de la forma $\{1,x,y\}$ con $x\in\{2,3,4\}.$ Hay tres con $y\in\{2,3,4\}$ y $3*32=96$ con $y\not\in\{2,3,4\},$ más el $\{2,3,4\},$ dando 100 en total.

Caso 2. $|I|=2.$

Podemos suponer que los conjuntos que no incluyen $1$ son precisamente $\{2,3,x\}$ para $x\in \{4,\dots,k\}$ con $k>4.$

Supongamos por ahora que no $A_j$ es igual a $\{1,4,5\}$ (lo que podría ocurrir si $k=5.$ ) Entonces todos los conjuntos que incluyen $1$ debe ser de la forma $\{1,2,y\}$ o $\{1,3,y\}$ para algunos $y,$ porque tienen que intersecar todos los conjuntos $\{2,3,x\}.$ Esto da un conjunto de la forma $\{1,2,3\}$ y $2*33=66$ otros incluyendo 1, y 33 conjuntos sin incluir 1. Es decir, 100 en total.

En el caso especial de que $k=5$ y algunos $A_j$ es igual a $\{1,4,5\},$ hay un conjunto más, pero ninguno de los conjuntos $\{1,2,y\}$ y $\{1,3,y\}$ pueden incluirse. Así que en ese caso apenas hay conjuntos, desde luego mucho menos de 100.

Caso 3. $|I|=1.$

Podemos suponer que todo conjunto que no incluya 1 contiene 2.

El primer subcaso es que dos triples que no incluyan 1 tengan una intersección de orden 1, $\{2,3,4\}$ y $\{2,5,6\}$ digamos. Entonces todo conjunto que contenga a 1 y que no acierte a 2 debe acertar a 3 ó 4 así como a 5 ó 6. Además algún conjunto no contiene 2 por lo que debe ser $\{1,3,5\}$ (intercambiando 3 y 4 si es necesario, y 5 y 6 si es necesario). Si ninguno de los conjuntos $\{1,3,6\},\{1,4,5\},\{1,4,6\}$ están en la familia, hay $34 + 1$ conjuntos que incluyen 1, y 65 que no incluyen 1 porque éstos deben contener 2 y 3 ó 5. Esto da 100. Si uno de los conjuntos $\{1,3,6\},\{1,4,5\},\{1,4,6\}$ está en la familia, entonces hay muchos menos conjuntos que contengan 2, es decir, mucho menos de 100 en total.

El otro subcaso es que todas las tripletas que contengan $2$ tienen una intersección de orden 2. Podemos suponer $\{2,3,4\}$ está en la familia, entonces un conjunto que no contenga 4, digamos $\{2,3,5\},$ y un conjunto que no contenga 3, que debe ser $\{2,4,5\},$ y no hay otros conjuntos que no contengan 1. Entonces no hay suficientes conjuntos que contengan 1: a lo sumo 34 que contengan 1 y 2, y a lo sumo otros tres.

Caso 4. $|I|=0.$

El primer subcaso es que dos triples que no incluyan 1 tengan una intersección de orden 1, $\{2,3,4\}$ y $\{2,5,6\}$ digamos. Hay otro conjunto que no incluye 2, digamos $\{3,5,x\}$ con $x\neq 2.$ Hay entonces a lo sumo siete conjuntos que incluyen 1 - $\{1,2,3\},\{1,2,5\},\{1,2,x\},\{1,3,5\},\{1,3,6\},\{1,4,5\},\{1,4,6\}$ - contradiciendo la suposición de que 1 está en al menos nueve conjuntos.

El otro subcaso es que todas las tripletas que no contengan 1 tengan una intersección de orden 2. Podemos suponer $\{2,3,4\}$ está en la familia, entonces un conjunto que no contenga 4, digamos $\{2,3,5\},$ y un conjunto que no contenga 3, que debe ser $\{2,4,5\},$ y luego $\{3,4,5\}.$ De nuevo, no hay suficientes conjuntos que contengan 1: como máximo $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\}.$