Associazioni...

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Associazioni...

Messaggioda Giovanni98 » 12/09/2015, 8:52

In un pianeta con almeno un abitante , ci sono delle associazioni. Ogni abitante appartiene ad almeno $k$ associazioni e comunque si prendano due associazioni il numero di persone che queste hanno in comune è $\leq 1$. Dimostrare che almeno $k$ associazioni hanno lo stesso numero di membri.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Associazioni...

Messaggioda Giovanni98 » 12/09/2015, 10:34

Qualcuno potrebbe gentilmente risolverlo dato che sono ormai due/tre ore che lo provo senza gloria :oops:
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Associazioni...

Messaggioda Delfad0r » 12/09/2015, 14:10

Bah, tre ore sono poche :mrgreen:
Comunque ecco il mio tentativo
Testo nascosto:
Innanzitutto eliminiamo le associazioni vuote che tanto sono inutili.
Poi prendiamo un'associazione $\Xi$ con il massimo numero di associati, diciamo $n$.
Consideriamo gli abitanti in $\Xi$: comunque presa una coppia di questi, i due elementi della coppia non possono avere associazioni in comune diverse da $\Xi$.
Dunque ognuno degli $n$ abitanti in $\Xi$ sta in almeno $k-1$ associazioni in cui non sta nessuno degli altri $n-1$; in altre parole, ci sono almeno $n(k-1)$ associazioni diverse da $\Xi$, quindi almeno $n(k-1)+1$ associazioni in tutto.
Ma ora notiano che la "cardinalità" di un'associazione può assumere al più $n$ valori distinti, quindi per pigeonhole ci sono almeno $k-1+1=k$ associazioni con la stessa "cardinalità".


EDIT: mi sono accorto ora che il testo dice che l'intersezione va fatta sulle associazioni, non sulle persone. Indi per cui la dimostrazione sopra è sbagliata. :oops:
EDIT2: in realtà è comunque fortuitamente giusta .-.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Associazioni...

Messaggioda Giovanni98 » 12/09/2015, 14:31

Dispiaciuto di vedere che bastava solo un'osservazione. Comunque grazie per la soluzione :).
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite