Intersezioni massimali [Insiemi]

[elgiovo]

Per $i=1,2,ldots,11$ sia $M_i$ un insieme, $|M_i|=5$. Per ogni $1<=i<j<=11$ sia $M_i cap M_j ne emptyset$.
Sia $m$ il numero più grande tale che esistano $M_(i_1),ldots,M_(i_m)$, soddisfacenti $\bigcap_{1<=k<=m} M_(i_k) ne emptyset$.
Si trovi il minimo valore di $m$ tra tutte le possibili scelte iniziali degli $M_i$.

[fields]

Buonsalve . Direi $m=4$.

Certamente $m>=4$. Lo dimostriamo, inutile dirlo, con il pigeonhole. Le buche sono gli elementi dell'insieme $M=uu{M_1,M_2,...,M_11}$, mentre i piccioni sono gli insiemi $M_1,M_2,...,M_11$. Poniamo l'insieme $M_i$ nella buca $a$ sse $a\in M_i$.

Facciamo vedere che esiste una buca che contiene almeno $4$ piccioni, ovvero almeno $4$ insiemi a intersezione non vuota. Supponiamo per assurdo il contrario, cioe' che ogni buca contenga al massimo $3$ piccioni. Mostriamo allora che ogni buca contiene esattamente $3$ piccioni, ottenendo chiaramente un assurdo, poiche' in questo caso le buche conterebbero in totale un numero di piccioni che sarebbe un multiplo di $3$, mentre invece le buche sono necessariamente riempite con esattamente $5\cdot 11=55$ piccioni. Bene, supponiamo esista una buca $a_1$ con meno di $3$ piccioni e sia $M_i$ in $a_1$. $M_i$ appartiene a $5$ buche $a_1,a_2,a_3,a_4,a_5$. In tali buche, oltre a $M_i$ ci possono essere al massimo altri $9$ insiemi per le ipotesi fatte. Cio' significa che $M_i$ ha intersezione vuota con qualche $M_j$, poiche' gli insiemi sono in totale $11$, assurdo.

Vediamo ora che $m=4$, producendo una collezione di $11$ insiemi a intersezione non vuota a coppie e in cui ogni quintupla di insiemi e' a intersezione vuota. L'esempio e' costruito a mano e al primo colpo, in accordo con l'intuizione che suggeriva fosse facile..

{1,2,3,4,5}
{1,6,7,8,9}
{2,6,10,11,12}
{3,7,10,13,14}
{4,8,11,13,15}
{5,9,12,14,15}
{1,5,10,13,16}
{2,6,14,15,16}
{3,7,9,11,16}
{4,8,7,12,16}
{5,9,12,13,15}

Forse esiste una collezione meno random, in questo caso aspetto di vederla da elgiovo

[elgiovo]

Salve. La risposta è corretta, e la soluzione mi è piaciuta. Ora ne mostro un'altra (strutturalmente e concettualmente molto simile).

Mostriamo che $m>=4$. Sia $X=\bigcup M_i$; per ogni $x in X$ sia $n(x)$ il numero di $i$ tali che $x in M_i$, $1<=i<=11$. Allora $m=max{n(x),x in X}$. Vale

$sum_(x in X)n(x)=55$.

Essendo $M_i cap M_j ne emptyset$, ci sono $((11),(2))=55$ intersezioni non vuote. D'altro canto, ogni elemento $x$ compare in $((n(x)),(2))$ intersezioni, dunque

$sum_(x in X) ((n(x)),(2))>=((11),(2))=55 rArr sum_(x in X)(n(x)(n(x)-1))/(2)>=55 rArr (m-1)/2 sum_(x in X) n(x)>=55$.

Dunque $(m-1)/2>=1 rArr m>=3$. Se $m=3$ valgono i segni di uguaglianza: $n(x)=m=3 forall x$. Ma dovendo essere $sum_(x in X) n(x)=55$, e poichè $3$ non divide $55$, $n(x)$ non può essere sempre $3$, quindi $m>=4$.
Ecco dunque l'esempio che prova $m=4$ (anche questo non dissimile da quello di fields, forse un pò più elegante ): consideriamo la tabella $4 times 4$

${: (a,b,c,d),(e,f,g,h),(1,2,3,4),(5,6,7,8):}$

Gli insiemi ${a,b,c,d,H}$, ${e,f,g,h,H}$, ${1,2,3,4,H}$, ${5,6,7,8,H}$ (insiemi orizzontali),
${a,e,1,5,V}$, ${b,f,2,6,V}$, ${c,g,3,7,V}$, ${d,h,4,8,V}$ (insiemi verticali),
${a,f,3,8,D}$, ${b,g,4,5,D}$, ${c,h,1,6,D}$ (insiemi diagonali)
soddisfano a tutto l'ambaradan, con $m=4$.

[fields]

Ecco dunque l'esempio che prova $m=4$ (anche questo non dissimile da quello di fields, forse un pò più elegante )

Decisamente piu' elegante e intuitivo