Insiemi sopra insiemi

[karlosson_sul_tetto]

(Non so se è la sezione giusta...)
(Kvant,1970,1,M5)
In un insieme E costitutito da n elementi, ci sono m sotto-insiemi diversi da E, tali che per ogni due elementi di E ci sarà esattamente un sottoinsieme, che comprende questi due elementi. DImostrare che $ m\geq n $. In che casi è possibile l'uguaglianza $ m=n $?

EDIT: corretto il TeX. ma_go

[ant.py]

Visto lo svarione di ieri, è possibile che stia dicendo cavolate, però:

Se n = 2, non c'è nessun sottoinsieme m diverso da E che contiene due elementi, quindi $ n \geq 3 $
Ora, il numero di combinazioni di n elementi presi a due a due (sarebbe il nostro m) è il coefficiente binomiale , e lo poniamo maggiore o uguale a n; si ha $ \binom{n}{2} \geq n $, ovvero $ n \geq 3 $, quindi a posto. Si ha n = m quando n = 3

[Claudio.]

Hai dimostrato che costruendo gli m in quella maniera funziona. Ma questo non basta affatto...devi dimostrare che comunque si costruiscano gli m vale sempre...per esempio se dimostrassi che costrurli come hai fatto è il modo "migliore", cioè il metodo che necessità di meno insiemi, allora andrebbe bene.

[ant.py]

Hai dimostrato che costruendo gli m in quella maniera funziona. Ma questo non basta affatto...devi dimostrare che comunque si costruiscano gli m vale sempre...per esempio se dimostrassi che costrurli come hai fatto è il modo "migliore", cioè il metodo che necessità di meno insiemi, allora andrebbe bene.

Certo, hai ragione.. E il metodo che ho descritto è effettivamente quello che richiede più insiemi di tutti.. Il metodo migliore è quello che, per ogni n, costruisce un sottoinsieme che comprende tutti gli elementi tranne uno, e n -1 insiemi che collegano questo elemento "escluso" a ogni altro, per un totale di n-1+1=n sottoinsiemi. Ancora non sono riuscito a dimostrarlo però..