Pagina 1 di 1
Signorina, lei deve assolutamente ballare con me ;)
Inviato: 25 lug 2006, 08:52
da enomis_costa88
In un paese A ci sono n ragazze e n ragazzi e ogni ragazza conosce ogni ragazzo.
Sia a(n,r) il numero di modi nei quali r ragazze possono danzare con r ragazzi in modo tale che ciascuna ragazza conosca il suo compagno.
In un paese B ci sono n ragazze e 2n-1 ragazzi tali che la ragazza i conosca i ragazzi 1,2,...,2i-1 (e nessun altro).
Sia b(n,r) il numero di modi nei quali r ragazze del paese B possono danzare con r ragazzi di B in modo tale che ciascuna ragazza conosca il suo compagno.
Dimostrare che a(n,r)=b(n,r)
Buon lavoro e buon ballo a tutti!!
Inviato: 07 ago 2006, 21:29
da chermit
Come devono essere scelte le r ragazze fra le n del paese B? A caso? E gli r ragazzi anche loro a caso?
Nel paese A non importa come si scelgono le ragazze o i ragazzi: tanto tutti conoscono tutti quindi la probabilità che l' i-ma ragazza delle r scelte a caso conosca tutti gli r ragazzi scelti a caso e pari a 1: quindi se non sbaglio a(n,r)=r^2 per tutte le possibili combinazioni tra gli insiemi di r ragazze e r ragazzi.
Ciao Chermit
Inviato: 09 ago 2006, 08:57
da enomis_costa88
chermit ha scritto:Come devono essere scelte le r ragazze fra le n del paese B? A caso? E gli r ragazzi anche loro a caso?
E' un conteggio chermit..quindi in tutti i modi possibili (ovviamente compatibili con le condizioni poste)
Ti faccio notare che sia a(n,r) che b(n,r) sono in funzione sia di r che di n.
In particolare $ a(n,r)\not=r^2 $
Inviato: 09 ago 2006, 19:55
da NM
Propongo questo metodo:
Si verifica prima che
$ a(n,r)=\binom{n}{r}^2r! $
fatto questo si può procedere a dimostrare il risultato per induzione su n usando questa relazione
$ b(n,r)=b(n-1,r)+(2n-r)b(n-1,r-1) $
che esprime il fatto che le combinazione relative ad r si possono contare come quelle che contengono la ragazza n_esima più quelle che non la considerano. Le prime combinazioni si calcolano facilmente, per le seconde si sceglie prima il posto per le r-1 ragazze e poi si posizione nei posti rimanenti (2n-r) l'n_esima.
Ci sono naturalmente un pò di punti (e di conti!) da sistemare (tipo il caso r=1 forse è bene farlo a mano per ogni n)...
Inviato: 09 ago 2006, 21:08
da enomis_costa88
NM ha scritto:si può procedere a dimostrare il risultato per induzione su n usando questa relazione
$ b(n,r)=b(n-1,r)+(2n-r)b(n-1,r-1) $
Si è la mia stessa idea!!
NM ha scritto:
Ci sono naturalmente un pò di punti (e di conti!) da sistemare
Chi è che vuole formalizzarlo per bene o cercare altre strade?