Tavola rotonda di pari opportunità
Tavola rotonda di pari opportunità
Ci sono m uomini ed n donne che si siedono attorno ad un tavolo rotondo (con m+n posti, ovviamente), cercando di fare in modo che non ci siano mai due donne una di fianco all'altra. Possono farlo? In quanti modi?
Chiaramente condizione necessaria affinché possano sedersi in quel modo è che $ m \geq n $.
Numero i posti da 1 a m+n.
Per ogni modo in cui le donne possono sedersi (anche senza rispettare la condizione) le ordino seguendo l'ordine crescente del numero del loro posto ottenendo così una sequenza $ p_1,p_2,...,p_n $ di posti occupati da donne.
Pongo $ p'_i=p_i-(i-1) $; allora le disposizioni buone sono in corrispondenza biunivoca con i sottoinsiemi di n elementi di $ (1,...,m+1) $ [come cavolo si fanno le graffe in TeX?] che sono $ \binom{m+1}n $. Questo non è però il numero che stavamo cercando, perché non abbiamo escluso i casi in cui l'unica coppia di posti adiacenti occupata da due donne sia $ (1,m+n) $; nel nostro insieme (1,...,m+1), questo equivale a dire che 1 e m+1 sono "occupati", e quindi a contare le possibili disposizioni per la restanti donne.
Il risultato è quindi $ \binom{m+1}n - \binom{m-1}{n-2} $
Che casino... spero si capisca almeno qualcosa.
Numero i posti da 1 a m+n.
Per ogni modo in cui le donne possono sedersi (anche senza rispettare la condizione) le ordino seguendo l'ordine crescente del numero del loro posto ottenendo così una sequenza $ p_1,p_2,...,p_n $ di posti occupati da donne.
Pongo $ p'_i=p_i-(i-1) $; allora le disposizioni buone sono in corrispondenza biunivoca con i sottoinsiemi di n elementi di $ (1,...,m+1) $ [come cavolo si fanno le graffe in TeX?] che sono $ \binom{m+1}n $. Questo non è però il numero che stavamo cercando, perché non abbiamo escluso i casi in cui l'unica coppia di posti adiacenti occupata da due donne sia $ (1,m+n) $; nel nostro insieme (1,...,m+1), questo equivale a dire che 1 e m+1 sono "occupati", e quindi a contare le possibili disposizioni per la restanti donne.
Il risultato è quindi $ \binom{m+1}n - \binom{m-1}{n-2} $
Che casino... spero si capisca almeno qualcosa.
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Aspetta.. tu hai detto che, se chiamo $ x_{(m,n)} $ il numero di modi di mettere m donne ed n uomini in modo che non siano attaccate le donne, allora ho che:what ha scritto: nel nostro insieme (1,...,m+1), questo equivale a dire che 1 e m+1 sono "occupati", e quindi a contare le possibili disposizioni per la restanti donne.
Il risultato è quindi $ \binom{m+1}n - \binom{m-1}{n-2} $
$ \displaystyle x_{(m,n)}=\binom{m+1}n - x_{(m-2,n-2)} $
giusto? A questo punto hai una ricorsione da sviluppare...
No, non mi sono spiegato.
Ci riprovo.
Contrassegno i posti con i numeri da 1 a m+n, li rappresento perciò con l'insieme $ P=\{1,...,m+n\} $.
Mettere a sedere le donne equivale a scegliere un sottoinsieme di P di n elementi.
Ad ogni possibile sottoinsieme $ \{a_1,a_2,...,a_n\} $ con $ a_1<a_2<...<a_n $ associo la n-upla $ \{b_1,b_2,...,b_n\} $ dove $ b_i=a_i-i+1 $. Allora il sottoinsieme di partenza non ha elementi consecutivi sse la n-upla ha tutti elementi distinti, ossia se la n-upla è un sottoinsieme di $ \{1,...,m+1\} $.
Abbiamo così $ \displaystyle \binom{m+1}n $ possibilità.
In tutto questo c'è però una falla: io ho contato i sottoinsiemi di P senza elementi consecutivi, ma non tutti vanno bene per il problema. Infatti potrebbe esserci una donna nel posto 1, una nel posto m+n e nessun'altra coppia adiacente. Queste configurazioni sono state contate nel procedimento di prima, ma non soddisfano il problema.
Quante sono?
Bè, per il mio sottoinsieme di P ho due scelte obbligate; per scegliere gli altri n-2 elementi in modo tale da non avere altri due elementi consecutivi, posso usare il trucco di prima. Guardo quindi la n-upla associata: si avrà $ b_1=1,b_n=m+1 $ con tutti gli elementi della n-upla distinti. Devo scegliere $ b_2,b_3,...,b_{n-1} $ fra gli elementi dell'insieme $ \{2,3,...,m\} $.
Pertanto $ \displaystyle \binom{m-1}{n-2} $.
Il numero delle combinazioni davvero buone è quindi $ \displaystyle \binom{m+1}n - \binom{m-1}{n-2} = $ $ \displaystyle \binom m n + \binom m{n-1} -\binom{m-1}{n-2} = \binom m n + \binom {m-1}{n-1} $
[scritto così è anche più carino
]
Ci riprovo.
Contrassegno i posti con i numeri da 1 a m+n, li rappresento perciò con l'insieme $ P=\{1,...,m+n\} $.
Mettere a sedere le donne equivale a scegliere un sottoinsieme di P di n elementi.
Ad ogni possibile sottoinsieme $ \{a_1,a_2,...,a_n\} $ con $ a_1<a_2<...<a_n $ associo la n-upla $ \{b_1,b_2,...,b_n\} $ dove $ b_i=a_i-i+1 $. Allora il sottoinsieme di partenza non ha elementi consecutivi sse la n-upla ha tutti elementi distinti, ossia se la n-upla è un sottoinsieme di $ \{1,...,m+1\} $.
Abbiamo così $ \displaystyle \binom{m+1}n $ possibilità.
In tutto questo c'è però una falla: io ho contato i sottoinsiemi di P senza elementi consecutivi, ma non tutti vanno bene per il problema. Infatti potrebbe esserci una donna nel posto 1, una nel posto m+n e nessun'altra coppia adiacente. Queste configurazioni sono state contate nel procedimento di prima, ma non soddisfano il problema.
Quante sono?
Bè, per il mio sottoinsieme di P ho due scelte obbligate; per scegliere gli altri n-2 elementi in modo tale da non avere altri due elementi consecutivi, posso usare il trucco di prima. Guardo quindi la n-upla associata: si avrà $ b_1=1,b_n=m+1 $ con tutti gli elementi della n-upla distinti. Devo scegliere $ b_2,b_3,...,b_{n-1} $ fra gli elementi dell'insieme $ \{2,3,...,m\} $.
Pertanto $ \displaystyle \binom{m-1}{n-2} $.
Il numero delle combinazioni davvero buone è quindi $ \displaystyle \binom{m+1}n - \binom{m-1}{n-2} = $ $ \displaystyle \binom m n + \binom m{n-1} -\binom{m-1}{n-2} = \binom m n + \binom {m-1}{n-1} $
[scritto così è anche più carino
]-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Ok ho capito, grazie del chiarimento 
Comunque immagino che così conti alcune configurazioni più volte (quelle uguali a meno di rotazioni)... mi sbaglio?
Consideriamo il problema così: abbiamo che ogni donna ha alla sua destra un uomo. Ora consideriamo questo nuovo problema: abbiamo $ n $ coppie DU e $ m-n $ uomini da disporre come ci pare attorno ad un tavolo (si può facilmente verificare la corrispondeza biunivoca. Quindi ora, "srotolando" il tavolo $ \binom mn $ modi di mettere queste persone. Tuttavia così contiamo ogni volta alcune configurazioni più volte... Ad esempio la configurazione:
(DU)UU(DU)U
è la stessa di
(DU)U(DU)UU
quindi è un po' incasinato!
Comunque immagino che così conti alcune configurazioni più volte (quelle uguali a meno di rotazioni)... mi sbaglio?
Consideriamo il problema così: abbiamo che ogni donna ha alla sua destra un uomo. Ora consideriamo questo nuovo problema: abbiamo $ n $ coppie DU e $ m-n $ uomini da disporre come ci pare attorno ad un tavolo (si può facilmente verificare la corrispondeza biunivoca. Quindi ora, "srotolando" il tavolo $ \binom mn $ modi di mettere queste persone. Tuttavia così contiamo ogni volta alcune configurazioni più volte... Ad esempio la configurazione:
(DU)UU(DU)U
è la stessa di
(DU)U(DU)UU
quindi è un po' incasinato!
-
mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
vi do la mia sol
allora, siccome coi binomiali ci devo prendere la mano co sti problemi se trovate qualcosa di semplificabile vi prego di farmlo notare ( anche se trovate qualcosa di errato )
cominiciamo
consideriamo le coppie del tipo DU.. esse sono messe in sequenza e tra due di queste adiacenti vi sono $ b\geqslant0 $ uomini
quindi abbiamo $ n!m!q $ combinazioni includendo le rotazioni dove q è il numer di modi in cui posso scrivere un somma di n termini il cui risultato sia m-n (cioè m-n uomini da sistemare in n spazi tra le coppie DU)
calcoliamo q
se mettiamo tutte le m-n U accanto e poi ne aggiungiamo altre n otteniamo che abbiamo$ \displaystyle{m-1 \choose n-1} $ di mettere n-1 separatori tra 2 U di modo che ra due separatori ci sia sempre almeno una U, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali ad 1 il cui valore è m, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali a 0 il cui valore è m-n...
pertanto il risultato cercato senza escludere le rotazioni è
$ \displaystyle n!m!{m-1 \choose n-1} $
mentre se si vuole escludere le rotazioni bisogna osservare che ogni disposizione è ripetuta ruotata tante volte quante sono le donne pertanto escludendo le rotazioni il risultato è
$ \displaystyle \frac{n!m!{m-1 \choose n-1}}{n}=(n-1)!m!{m-1 \choose n-1 $
)cominiciamo
consideriamo le coppie del tipo DU.. esse sono messe in sequenza e tra due di queste adiacenti vi sono $ b\geqslant0 $ uomini
quindi abbiamo $ n!m!q $ combinazioni includendo le rotazioni dove q è il numer di modi in cui posso scrivere un somma di n termini il cui risultato sia m-n (cioè m-n uomini da sistemare in n spazi tra le coppie DU)
calcoliamo q
se mettiamo tutte le m-n U accanto e poi ne aggiungiamo altre n otteniamo che abbiamo$ \displaystyle{m-1 \choose n-1} $ di mettere n-1 separatori tra 2 U di modo che ra due separatori ci sia sempre almeno una U, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali ad 1 il cui valore è m, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali a 0 il cui valore è m-n...
pertanto il risultato cercato senza escludere le rotazioni è
$ \displaystyle n!m!{m-1 \choose n-1} $
mentre se si vuole escludere le rotazioni bisogna osservare che ogni disposizione è ripetuta ruotata tante volte quante sono le donne pertanto escludendo le rotazioni il risultato è
$ \displaystyle \frac{n!m!{m-1 \choose n-1}}{n}=(n-1)!m!{m-1 \choose n-1 $
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"
Galileo Galilei
Galileo Galilei
un'altra soluzione...
ordino prima gli m uomini intorno al tavolo; poichè non voglio considerare le rotazioni del tavolo, divido tale valore per m. i modi per fare questo sono:
$ \frac{m!}{m}=(m-1)! $
ora ho esattamente $ m $ modi per far sedere la prima donna (perchè questa puo' stare tra 2 uomini qualunque); $ m-1 $ modi per far sedere la seconda donna (perchè puo' sedere tra 2 uomini qualunque esclusi i due tra cui è seduta la prima donna);... $ m-n+1 $ modi per far sedere l'n-esima donna. Dunque i modi di far sedere le donne sono:
$ m(m-1)...(m-n+1)=\frac{m!}{(m-n)!} $
Moltiplicando questo valore per il numero di modi di far sedere gli uomini, si ha il risultato di mattilgale:
$ \frac{(m-1)!m!}{(m-n)!} $
Ciao!
Maria
ordino prima gli m uomini intorno al tavolo; poichè non voglio considerare le rotazioni del tavolo, divido tale valore per m. i modi per fare questo sono:
$ \frac{m!}{m}=(m-1)! $
ora ho esattamente $ m $ modi per far sedere la prima donna (perchè questa puo' stare tra 2 uomini qualunque); $ m-1 $ modi per far sedere la seconda donna (perchè puo' sedere tra 2 uomini qualunque esclusi i due tra cui è seduta la prima donna);... $ m-n+1 $ modi per far sedere l'n-esima donna. Dunque i modi di far sedere le donne sono:
$ m(m-1)...(m-n+1)=\frac{m!}{(m-n)!} $
Moltiplicando questo valore per il numero di modi di far sedere gli uomini, si ha il risultato di mattilgale:
$ \frac{(m-1)!m!}{(m-n)!} $
Ciao!
Maria
Devo dire che mi hai un po' confuso... in effetti io pensavo che i posti a sedere non fossero indistinguibili, e che quindi le configurazioni uguali a meno di rotazioni fossero diverse.Simo_the_wolf ha scritto:Ok ho capito, grazie del chiarimento
Comunque immagino che così conti alcune configurazioni più volte (quelle uguali a meno di rotazioni)... mi sbaglio?
Consideriamo il problema così: abbiamo che ogni donna ha alla sua destra un uomo. Ora consideriamo questo nuovo problema: abbiamo $ n $ coppie DU e $ m-n $ uomini da disporre come ci pare attorno ad un tavolo (si può facilmente verificare la corrispondeza biunivoca. Quindi ora, "srotolando" il tavolo $ \binom mn $ modi di mettere queste persone. Tuttavia così contiamo ogni volta alcune configurazioni più volte... Ad esempio la configurazione:
(DU)UU(DU)U
è la stessa di
(DU)U(DU)UU
quindi è un po' incasinato!
In più, leggendo le altre soluzioni, mi pare che addirittura gli uomini fra di loro siano da considerarsi distinti!
Insomma, del problema originale non ci ho capito una mazza!
A parte questo volevo sapere: come faccio leggendo un problema simile a decidere se devo contare o meno le rotazioni, o se devo considerare le donne diverse fra loro oppure no?
Eh, lo so, quel problema è, a dir poco ambiguo.
La tua soluzione è giusta se si considerano distinte due disposizioni che si sovrappongono per rotazione.
I risultati di Leblanc e mattilgale effettivamente considerano distinguibili tra loro gli uomini (o le donne), ma identificano disposizioni che differiscono di una rotazione del tavolo.
A questo punto, visto che ci siamo, non è che qualcuno mette insieme i due risultati?
Insomma, considerando indistinguibili le persone dello stesso sesso e considerando due disposizioni identiche se differiscono di una rotazione, quanti modi di mettersi a tavola ci sono?
PS : effettivamente sì, il problema era sul libro delle olimpiadi italiane e li veniva risolto senza pensare alle rotazioni (il che è un poco assurdo in quanto il testo parla di tavolo rotondo).
La tua soluzione è giusta se si considerano distinte due disposizioni che si sovrappongono per rotazione.
I risultati di Leblanc e mattilgale effettivamente considerano distinguibili tra loro gli uomini (o le donne), ma identificano disposizioni che differiscono di una rotazione del tavolo.
A questo punto, visto che ci siamo, non è che qualcuno mette insieme i due risultati?
Insomma, considerando indistinguibili le persone dello stesso sesso e considerando due disposizioni identiche se differiscono di una rotazione, quanti modi di mettersi a tavola ci sono?
PS : effettivamente sì, il problema era sul libro delle olimpiadi italiane e li veniva risolto senza pensare alle rotazioni (il che è un poco assurdo in quanto il testo parla di tavolo rotondo).
-
mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta: