Sia fissato un intero $n\ge 2$ e sia $S_n:=\{1,2,\ldots,n\}$. Un insieme $A$ e' detto ammissibile se esistono degli interi $1\le x < y\le n$ tale che $A=S_n\cap [x,y]$. Sia $\mathcal{A}$ una famiglia di insiemi ammissibili distinti tali che
\[ A_i\cap A_j \in \mathcal{A}, \text{ per ogni } A_i, A_j \in \mathcal{A} \]
Mostrare che $\displaystyle |\mathcal{A}|\le \left\lfloor \frac{n^2}{4} \right\rfloor$
$\displaystyle |\mathcal{A}|\le\lfloor\frac{n^2}{4} \rfloor$
$\displaystyle |\mathcal{A}|\le\lfloor\frac{n^2}{4} \rfloor$
The only goal of science is the honor of the human spirit.
Re: $\displaystyle |\mathcal{A}|\le\lfloor\frac{n^2}{4} \rfl
Si nota che ogni famiglia $ \mathcal{A} $ deve ammettere un insieme di cardinalità minima, che però non può coincidere con l'insieme vuoto, questo insieme ha la forma $ A_k=S_n\cap [x,x+1] $. Per ipotesi si aveva che $ A_i\cap A_j \in \mathcal{A}, \text{ per ogni } A_i, A_j \in \mathcal{A} $, ma questo equivale a dire in questo caso che, supposto $ |\mathcal{A}|=m $, $ \displaystyle\bigcap_{i=1}^{m} A_i=A_k $. Infatti se $ A_l=A_i\cap A_j \in \mathcal{A} $, allora anche $ A_l\cap A_p=A_i\cap A_j\cap A_p \in \mathcal{A} $ e così via. Se l'insieme minimo fosse del tipo $ [x,x+k] $ con $ k>1 $,allora alla famiglia non potrebbe appartenere $ A_k=[x,x+1] $ che è assurdo, poichè se $ A_k \in \mathcal{A} $ anche $ [x,x+1] \cap [x,x+k] \in \mathcal{A} $, in quanto $ [x,x+1] \cap [x,x+k]=[x,x+1]=A_k $, da questo segue che $ A_k $ esiste ed è il minimo.
Adesso proviamo a contare la cardinalità di una famiglia di insiemi.
Prefissato un un intervallo minimo, ovviamente del tipo $ [x,x+1] $, allora il numero degli insiemi appartenenti alla famiglia è dato dal prodotto di tutti i possibili modi di scegliere il primo elemento dell'intervallo in modo che sia minore o uguale ad $ x $, per tutti i possibili modi di scegliere l'ultimo elemento dell'intervallo maggiore o uguale ad $ x+1 $.
Abbiamo quindi che $ |\mathcal{A}|=x\cdot (n-x) $. E' sufficiente mostrare che $ \max{|\mathcal{A}|}\le \displaystyle\left\lfloor \frac{n^2}{4} \right\rfloor $.
Massimizziamo il prodotto $ x\cdot (n-x) $.
Per AM-GM si ha che $ \dfrac{n}{2}\ge \sqrt{x(n-x)} $ da cui al massimo, trattandosi di interi positivi, $ \displaystyle\left\lfloor \frac{n^2}{4} \right\rfloor=x(n-x) $.
Da cui la tesi: $ \displaystyle |\mathcal{A}|\le \left\lfloor \frac{n^2}{4} \right\rfloor $.
Adesso proviamo a contare la cardinalità di una famiglia di insiemi.
Prefissato un un intervallo minimo, ovviamente del tipo $ [x,x+1] $, allora il numero degli insiemi appartenenti alla famiglia è dato dal prodotto di tutti i possibili modi di scegliere il primo elemento dell'intervallo in modo che sia minore o uguale ad $ x $, per tutti i possibili modi di scegliere l'ultimo elemento dell'intervallo maggiore o uguale ad $ x+1 $.
Abbiamo quindi che $ |\mathcal{A}|=x\cdot (n-x) $. E' sufficiente mostrare che $ \max{|\mathcal{A}|}\le \displaystyle\left\lfloor \frac{n^2}{4} \right\rfloor $.
Massimizziamo il prodotto $ x\cdot (n-x) $.
Per AM-GM si ha che $ \dfrac{n}{2}\ge \sqrt{x(n-x)} $ da cui al massimo, trattandosi di interi positivi, $ \displaystyle\left\lfloor \frac{n^2}{4} \right\rfloor=x(n-x) $.
Da cui la tesi: $ \displaystyle |\mathcal{A}|\le \left\lfloor \frac{n^2}{4} \right\rfloor $.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »