Intersezioni non vuote
Sia $n \ge 2$ un intero e sia $X$ un insieme di $n$ elementi. Siano $A_1, A_2,...,A_{101}$ sottoinsiemi di $X$ tali che l'unione di ogni 50 abbia piu` di $(50n)/51$ elementi. Dimostrare che esistono tre degli $A_i$ tali che le intersezioni di ogni due siano non vuote.
Risposte
Nel caso qualcuno fosse ancora interessato, posto un hint:
Cosa significa intersezioni non vuote? Che argomento è?
Significa che hanno almeno un elemento in comune.
Combinatoria.
Combinatoria.
Mmm... siamo sicuri che il risultato parziale non sia che esistono almeno $52$ insiemi con piu' di $n/51$ elementi? (questo dovrebbe essere conseguenza del fatto che per ogni scelta di $50$ tra i $101$ insiemi deve esistere un insieme con piu' di $n/51$ elementi)...
E che la vera tesi non sia che esistono tre insiemi che hanno intersezione comune non nulla?
E che la vera tesi non sia che esistono tre insiemi che hanno intersezione comune non nulla?
È giusto come è.
Azz... allora ho fatto un errore nel ragionamento. Provo a scriverlo.
Fatto 1: per ogni scelta di 50 tra i 101 insiemi esiste un insieme con più di n/51 elementi.
Verifica fatto 1: presi 50 di questi insiemi, se tutti avessero meno di n/51 elementi, la loro unione avrebbe meno di n*50/51 elementi, il che non è possibile. Esiste quindi almeno un insieme con almeno n/51 elementi.
Fatto 2: esistono almeno 52 insiemi con piu' di n/51 elementi. Sia K l'insieme di questi insiemi.
Verifica fatto 2: prendiamo 50 insiemi tra i 101. Esiste per il fatto 1 un insieme con piu' di n/51 elementi. Ora mettiamolo da parte. Tra i rimanenti 100 ne scegliamo 50 e tra questi troviamo, sempre per il fatto 1, almeno un insieme con almeno n/51 elementi. Lo mettiamo da parte... Quando ne abbiamo messi da parte 51, ne rimarranno 50 e sarà l'ultima volta che si può applicare la procedura... e allora ne avremo trovati 52!
Ora scrivo come volevo procedere, ma penso di avere trovato l'errore mentre scrivevo
:
Prendiamo gli insiemi K. Ora o esiste una casella che appartiene a tre di questi insiemi, e allora abbiamo concluso, oppure esistono piu' di (n/51*52-n)=n/51 caselle che appartengono a due di questi insiemi. Consideriamo queste caselle. Scegliendo ora un qualsiasi insieme di 50 insiemi, abbiamo che almeno uno tra questi deve intersecare almeno una di queste n/51 caselle. Scegliendo questo insieme ed i due appartenenti a K che contengono la suddetta casella abbiamo tre insiemi che contengono la medesima casella. L'errore credo stia che non si riesce a completare questo ragionamento mostrando che il terzo insieme sia effettivamente diverso dagli altri due
Fatto 1: per ogni scelta di 50 tra i 101 insiemi esiste un insieme con più di n/51 elementi.
Verifica fatto 1: presi 50 di questi insiemi, se tutti avessero meno di n/51 elementi, la loro unione avrebbe meno di n*50/51 elementi, il che non è possibile. Esiste quindi almeno un insieme con almeno n/51 elementi.
Fatto 2: esistono almeno 52 insiemi con piu' di n/51 elementi. Sia K l'insieme di questi insiemi.
Verifica fatto 2: prendiamo 50 insiemi tra i 101. Esiste per il fatto 1 un insieme con piu' di n/51 elementi. Ora mettiamolo da parte. Tra i rimanenti 100 ne scegliamo 50 e tra questi troviamo, sempre per il fatto 1, almeno un insieme con almeno n/51 elementi. Lo mettiamo da parte... Quando ne abbiamo messi da parte 51, ne rimarranno 50 e sarà l'ultima volta che si può applicare la procedura... e allora ne avremo trovati 52!
Ora scrivo come volevo procedere, ma penso di avere trovato l'errore mentre scrivevo
:Prendiamo gli insiemi K. Ora o esiste una casella che appartiene a tre di questi insiemi, e allora abbiamo concluso, oppure esistono piu' di (n/51*52-n)=n/51 caselle che appartengono a due di questi insiemi. Consideriamo queste caselle. Scegliendo ora un qualsiasi insieme di 50 insiemi, abbiamo che almeno uno tra questi deve intersecare almeno una di queste n/51 caselle. Scegliendo questo insieme ed i due appartenenti a K che contengono la suddetta casella abbiamo tre insiemi che contengono la medesima casella. L'errore credo stia che non si riesce a completare questo ragionamento mostrando che il terzo insieme sia effettivamente diverso dagli altri due
va bè dai magari qualcuno riprende da lì e conclude 
Mmm... provo di nuovo, partendo dal fatto 2.
Consideriamo un insieme (inizialmente generico) $k$ appartenente a $K$. Possiamo vedere che esistono almeno $51$ insiemi che lo intersecano (con un ragionamento analogo a quello fatto per provare il fatto 2), chiamiamo $X$ l'insieme di questi insiemi. Inoltre tra questi $51$ possiamo supporre (scegliendo opportunatamente $k$) che uno tra questi appartenga anche lui a $K$, chiamiamolo $k'$.
A questo punto escludendo $k'$ rimanengono $50$ insiemi appartenenti a $X$. Almeno uno tra questi intersechera' $k'$. Questo insieme, unito a $k'$ e $k$ dovrebbe comporre la nostra terna... forse...
Ok passo e chiudo per oggi...
Consideriamo un insieme (inizialmente generico) $k$ appartenente a $K$. Possiamo vedere che esistono almeno $51$ insiemi che lo intersecano (con un ragionamento analogo a quello fatto per provare il fatto 2), chiamiamo $X$ l'insieme di questi insiemi. Inoltre tra questi $51$ possiamo supporre (scegliendo opportunatamente $k$) che uno tra questi appartenga anche lui a $K$, chiamiamolo $k'$.
A questo punto escludendo $k'$ rimanengono $50$ insiemi appartenenti a $X$. Almeno uno tra questi intersechera' $k'$. Questo insieme, unito a $k'$ e $k$ dovrebbe comporre la nostra terna... forse...
Ok passo e chiudo per oggi...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo