OliForum Matematico

Trova il massimo intero $ n $ per cui esistono $ n $ insiemi distinti $ S_1,S_2,\dots,S_n $ tali che:

$ |S_i \cup S_j|\leq 2004 $ per ogni $ 1\leq i < j\leq n $
$ S_i\cup S_j \cup S_k =\{1,2,\dots,2008\} $ per ogni $ 1\leq i < j<k\leq n $

Creiamo una tabella, con righe numerate con "r": da 1 a 2008 (elementi dell'insieme Universo); e con le colonne "c":da 1 a n (gli Si).
Scriviamo in (r, c) la cifra 1 se $ r\in c $; scriviamo 0 altrimenti.
Contiamo le terne (r, c1, c2) tali che (r, c1)=(r, c2)=0. Siano esse T.

Notiamo che dalla seconda ipotesi, un elemento non può non essere contenuto in 3 insiemi distinti, dunque ogni riga contiene al più 2 zeri. $ T\leq 2008 $.

La prima ipotesi dice, invece che per ogni coppia di insiemi-colonne, ci sono almeno 4 elementi che non appartengono a nessuno di questi insiemi. Pertanto ad ogni coppia di colonne ci sono almeno 4 triplette. Quindi $ T\geq 4C_{n,2} $.

Mettendo insieme queste considerazioni, si risolve con $ n\leq 32 $.
Un esempio si costruisce con la tabella in cui 24 righe si riempiono di uni, mentre le restanti 1984 si dividono in 4 gruppi di $ C_{32,2} $, nei quali ogni riga è associata ad una corrispondente coppia di colonne: tale riga avrà le caselle corrispondenti a quella coppia =0, mentre sarà =1 altrove.


Domanda bonus
Dato n (minore di 33, s'intende), quante sono le collezioni (ordinate) di n insiemi che soddisfano le ipotesi (con =2004, al posto di $ \leq $) ?